東京海上日動プログラミングコンテスト2023（AtCoder Beginner Contest 304）に参加しました。
結果
A,B,C,D,Eの5問正解でした。
D問題を提出した辺りからジャッジが詰まっていたみたいで結果が全然分からなかった。
おかげで正解しているかどうかわからないのでやり辛かった。
まだDDoS仕掛けられているのかなあ
E問題まで解けたのにUnratedなのは残念
A - First Player
円卓に人が座っているので最年少の人を始点に全員分の名前を順番に出力する問題。
ループ処理と数値の大小比較ができれば解ける問題だと思う。
1回目のループ処理で最年少の人が何番目にいるのかを探して、2回目のループでその人を始点にN人分の名前を順番に出力すれば良い。
配列の引数は1大きくしつつ、Nで割った余りを使えば配列外参照になることなくN-1番目の次に0番目を参照できる。
B - Subscribers
与えられた整数の値によって指定された桁数以下を切り捨てて表示させる問題。
if文とかで条件を正しく処理できれば解ける問題だと思う。
愚直に問題文の通り大小関係を確認してどのパターンの処理をすれば良いか判断する。
X桁以下を切り捨てにする部分は、で割った余りを引いて処理した。
C - Virus
人の座標が与えられ、距離D以内の人に感染するウイルスが1番目の人に感染したので、最終的に各人がウイルスに感染するかどうかを答える問題。
人を頂点、人iと人jの距離がD以内の場合はその2頂点が辺で繋がっているとみなして、人1と同じ連結成分に含まれているかどうかを答える問題だとみなして解いた。
1度全ペアの距離を計算する必要があるが、制約的にTLEにはならないので連結成分を作る部分や、任意の人が連結成分に含まれているかどうかを判断する部分の処理が重くなければ解き切れると思う。
D - A Piece of Cake
指定された方法で長方形のケーキを切り分けるので切り分けたあとのケーキに乗っているいちごの数の最大と最小を答える問題。
xy-平面で軸に対して平行に切り分けるので切り分けたあとのケーキに番号を振って、いちごの座標を基にどの番号のケーキに乗っているのかを判断し、何番のケーキに何個いちごが乗っているのかを数えて、最終的にいちごの数の最大と最小を答えれば正解できた。
いちごの座標は、二分探索で何番目と何番目の切れ目の間にあるのかを軸ごとに探索して、それをもとにケーキの番号を計算した。
いちごの数ははじめは配列で管理していて、サイズがの配列を用意して解こうとしけど、提出してみるとREになった。
多分サイズが大きすぎて配列が確保できなかったのかなと思い、別の解き方を考えることにした。
計算したケーキの番号はsetで記録して、ケーキごとのいちごの数はmapで管理することにしてみた。
setのサイズがと一致するならsetに記録されている最大N個のケーキ番号をもとにmapで管理している各ケーキのいちごの数を確認して最大値と最小値を管理して、
setのサイズが
より小さいなら必ずいちごが0個のケーキがあって最小値が0になる。
最後に管理している最大と最小を答えた。
E - Good Graph
グラフが与えられるので指定された頂点2つをつなぐ辺を付け加えた場合、
予め設定されている複数の頂点ペアをつなぐパスが存在しないかどうかを答える問題。
※最初は予め設定されている複数の頂点ペアをつなぐパスが存在しない。
質問はQ個あってなので各質問にはO(N)よりも早く処理しないとTLEしそうだと思った。
うまい方法がしばらく思いつかなかったけどテストケースを手書きして考え見ると、
辺で繋がっている頂点を1つグループとみなすと、一部のグループ間では辺を貼ってはいけないという設定で
このグループ間で辺を貼ってよいかどうかを答える問題に見えたので、Union-Findを使って解くことにした。
普通のUnion-Findで連結成分を作り、パスを作っては行けない頂点のroot同士でペアを作りsetで管理した。 Q個の質問で指定された頂点に対してもそれぞれのrootを探してその組み合わせがsetで管理しているペアに含まれているかどうかを探してYes/Noを答えた。
提出してみたらコンテストが終了してもジャッジが詰まっていてACかどうかが全く分からず心配だったけど無事正解しててよかった。
