ABC 304 東京海上日動プロコン　感想記

結果

A~Eの5完でした。
最近いい感じの回に限ってUnratedになって悲しいですよ(😢ｵｲｵｲ)
A~Eで全体1300位ぐらいだったんで昔よりレベルあがってる感を感じる最近です
(順位上げたかったら早解き必要そうですね)

A -First Player

A-First Player

年齢最小のひとを見つけて、そこから順にN人表示すればよい。
スライス使える言語なら、先頭より手前を後ろにくっつけてfor文回したほうがコード少なそう。
計算量は$O(n)$

B -Subscribers

B-Subscribers

$d(N)$をNの桁数としたとき、$10^{d(N)-2}$で切り捨てすればよい。
計算量は$O(log(N))$

C -Virus

C-Virus

1番目の人を始点に、BFSの要領で感染する人を探索すればよい。
$d(x,y)^2 <= D^2$として、整数値で比較を行い誤差が出ないようにすることに注意。
( $d(x,y)$　:= $x$, $y$番目の人の間の距離 )
計算量は$O(N^2)$

D -A Piece of Cake

D-A Piece of Cake

マス目は数が大きすぎるのでマス目を基準に数えるのはNGなので、イチゴを基準として考える。
二部探索によって各イチゴが所属する横のマス目、縦のマス目が$O(log(W or H))$で求められる。
よって、各マス目に存在するイチゴの数をmapによって記憶すればよい。
ここで、mapのサイズが$(A+1)(B+1)$未満である場合はイチゴが0こであるマス目が存在するため、最小値が0となることに注意。
計算量は$O(N(log(H)+log(W))+log(N))$

E -Good Graph

E-Good Graph

制約的に、各クエリにO(log(N))程度で答えられなけらばならない。
まず、Union-Findを用いることで各頂点と連結である頂点のグループに分けられる。
頂点$p$と$q$それぞれに良いグラフを壊すペアが含まれているかが判定できれば、新しいグラフが良いグラフかどうかわかる。
しかし、これを愚直に考えると難しいため少し考え方を変え、「各グループが連結となってはダメなグループ」を考える。
例えば$x_{i}$がグループ$a$、$y_{i}$がグループ$b$に属する場合はグループaとグループbは連結となってはいけない。よって、これらをvector<set>に記憶し、$p_{i}$が属するグループのsetに$q_{i}$が属するグループが含まれていないかを判定することで1つのクエリに$O(log(n))で答えることができる。
(各setのサイズは$(O(n))$)