AGC014 A,B,C,D
公式解説(pdf)
Editorial - AtCoder Grand Contest 014 | AtCoder
公式動画解説
www.youtube.com
A問題
問題の得点からそんな難しい問題ではないだろうと決め打ちしてlog_2(max(a, b, c))回でシミュレーションが実行できそうだと考えた。10^7回シミュレートして終わらなかったら-1を出力した。ちょっと勘違いして実装に時間をかけてしまった。
B問題
いくら手元で実験を繰り返しても思い浮かばず50分経過くらいで順位表を見たらすぐにWAも出さず解いてる人がいたので実は簡単なのではと思い考え直す。1と全ての他の頂点がつながっている木を試すとこのグラフのみでYes、Noが判定できるのではと思い提出したら通った。コンテスト後のtwitterを見ていた限り証明しないで（順位表を見て）出したらACだった人が多かった。
C問題
コンテスト中は問題文読んだ時点で難しそうだったのでスルーした。割と発想ゲーだったように思えたのでもうちょっと考えればよかった。最初にK回移動し、残りの魔法は壁をK回壊し、K回進むと考えると一番近い辺に直進するのがいいことがわかる。K回の移動でたどり着ける範囲をBFSで列挙し、辺にたどり着くまでの魔法の使用回数が最も少ない点を選ぶ。
D問題
次数1の頂点に2つ以上隣接している頂点があればFirstを返すコードをとりあえずで出したら予想外にACのテストケースが多くこの方針にコーナーケース対策を追加する方針で考え始めたのが終わりの始まりだった…隣接している頂点が全て次数1の頂点に隣接している頂点があるときFirstを返す（次数1の頂点からの距離が3以上でも白く塗れるケースはあるのでWA）、ある頂点が最終的に白く塗れるかどうかを葉の方に向かってDFSをすべての頂点に行う（O(n^2)で当然TLE）と考えたところでコンテスト終了。
中心の点から考えるのではなく葉から貪欲に考えることでO(n)で解ける。葉を黒く塗り隣接している頂点を白く塗る。そして塗った頂点をグラフから切り離す。このとき次数0の頂点が存在すればFirst、存在せず最後まで塗ることができればSecondを出力する。
グラフに完全マッチングが存在すれば白く塗った頂点とマッチングで繋がれた頂点を黒く塗ることで、すべての白く塗った頂点に隣接する頂点を黒く塗ることができる。よって完全マッチングが存在することと後手必勝は同値。
葉から探索を始める、完全マッチングといった発想は覚えておきたい。
