はまやんはまやんはまやん

hamayanhamayan's blog

AtCoder Grand Contest 014 解説

http://agc014.contest.atcoder.jp

以下、解説





















A. Cookie Exchanges

http://agc014.contest.atcoder.jp/submissions/1267558
300点だから、シミュレーションだろうと思って実装。
上限を定めておいて、上限になったら無限に続くものとする。

B. Unplanned Queries

http://agc014.contest.atcoder.jp/submissions/1267731
N頂点の木ではなく、N頂点の鎖(パス状)で考えてみると、辺のコストが偶数となる場合は、全ての頂点が偶数回使われている時であると分かる。
これが必ず言えるか分からないが、Submit検証するとACする。

C. Closed Rooms

http://agc014.contest.atcoder.jp/submissions/1268285
移動->消すのグループだが、これを、消す->移動のグループとして考える。
Kマス消してKマス移動するということは、もはや壁は問題にならないということ。
なので、最初のK回の移動で移動できるマス全てに対して、一直線に端へ向かったときの最小魔法回数を探索すれば良い。

D. Black and White Tree

http://agc014.contest.atcoder.jp/submissions/1268182
解説にあるように次数1の頂点の1つ前を白に塗って次数1の頂点を黒に塗ってを貪欲に繰り返していく。
次数1の頂点の1つ前が既に白に塗られていて、次数1の頂点が塗られていないならFirstが勝ちで基本はOK。
実装によっては、こういうコーナーケースがある

5
1 2
2 3
3 4
4 5
答えFirst

完全マッチングが想定解

E. Blue and Red Tree

http://agc014.contest.atcoder.jp/submissions/1268786
考察は解説放送を見ましょう。それが一番良いです。
実装面の話をします。

rngさんが「次数の小さい方の辺を次数の大きい方の辺に移し替えるとO(logN)になる有名な話」と言っているのは「マージテク」のこと。
hamayanhamayan.hatenablog.jp
辺を追加する時に既にある場合はマージすることにする。
マージは次数の小さい方の頂点の辺を大きい方の頂点にくっつけるようにやる。
この時、再度二重辺ができた場合は再帰的にマージしていく。
これでAC