AGC017 - D - Game on Tree
概要
サイズNの木が与えられ、頂点には１～Nまでの番号が振られてる。AliceとBobはAliceからゲームを始め、自分の手番が終わったら、相手に交代する。自分の手番では、次の操作を行う。
- 木の辺を1本取り除く。これによって、木は2つの部分木に分かれるが、そのうち頂点1を含む方のみを残す。
操作が行えなくなったら、その時点でその人は負けとなる。
誰が必勝なのだろうか？
制約： 1 <= N <= 10^5
ACするまで
1. 手元でいろいろ実験をしてみると、頂点1から出る枝ごとに、いろんな条件があるのかなぁ。。。と思うも、いまいち決定的なポイントがつかめない。
2. そもそも、ゲーム問題での定石として、Grundy数が定義できるなら問題ないため、定義してみる。
3. ちょっと考えると定義できるため、書く->AC!
考察
この考察はGrundy数を理解してる前提で書きます。
まず、Grundy数の性質により、ある頂点から例えば、3つに枝分かれした時、その3つをそれぞれ独立なゲームとして考えて、その結果をXORすると、その点でのGrundy数が分かる。木構造の枝分かれを複数のゲームとみなしてる。
さて、1つのゲームは、上のように枝分かれをうまく処理すると、一列に連なるグラフのようなものの勝敗を考えることになる。
よって、これを実装すればよい。
一言
Grundy数と木の上のゲームの相性抜群だなぁ。。。
