AtCoder Grand Contest 014

参加しました。

A問題 Cookie Exchanges

3人がクッキーをA,B,C枚持っている時、各々が半分ずつ他の二人に渡す操作は何回できるか（奇数になったら終わり）という問題。

A,B,C → (B+C)/2,(A+C)/2,(A+B)/2になるので、二人の個数の差は1回の操作で1/2になる。よってシュミレーションすればlog(A,B,C)でいけるという感じ。（3人とも同じ枚数なら無限に続く)

B問題 Unplanned Queries

N点の木に対してまず各辺に0をふった後、M個のクエリをやる。

「a_i,b_iの2頂点間のパスに現れる辺にふってある数字を+1する」

全部の辺にふってある数字が偶数になるような木は存在するかという問題。

なんとなくa_i,b_iに現れる数字の回数の偶奇がそのまま関係してそうだったので、全部偶数回か調べたら通りました（）。

C問題 Closed Rooms

H行W列の部屋があり、移動は接する部屋のみ。閉じている部屋と開いている部屋が最初存在していて、1,H行目、1,W列目についたらゴール。

K部屋以下分移動し、K個以下の部屋を開けるという魔法を何回使えばゴールできますかという問題。

K個部屋開けてK部屋進むという一連の操作で直進し続けられるので、初期状態でK部屋以下分移動した時に、どこまでゴールに近づけるかさえわかれば良い。

queueを使って行ける部屋を管理してみました。

バグらせて時間を結構使ったけど通ったのでよし。

D問題は端から貪欲に取っていけばいいということはわかりましたがバグらせました。（終わった後普通に通ったので、ダメ）

208位　パフォーマンス2118 レート2021(+12)

いつ黄色から落ちるかのチキンレース