AGC033 C - Removing Coins
解法
それぞれのターンで、ある頂点を指定すると、その頂点を根とする木について、葉になっている頂点が消えることになります。
そして、どのような頂点の選び方をしても、木についている頂点を減らすのに一番時間がかかる部分は、木の直径の部分です。ある頂点を選んだ際、一番遠くに存在するコインは、もちろんその頂点からの距離が一番遠いものになります。その頂点は、必ず木の直径の端点になっている(この問題の解説に載っています)ので、ネックになるのは木の直径です。
ということで、木の直径が勝敗に関係していそう、ということがわかったので、木の直径がどのような場合に勝敗がどうなっているかを調べます。
- 直径が0の場合
頂点が1個の場合です。もちろん、先手がコインを取って終了なので、先手の勝ちです。
- 直径が1の場合
頂点が2個です。もちろん、先手と後手が1回ずつコインを取って終了です。後手の勝ちになります。
直径が2の場合
図のように、真ん中を選択すると、直径が0のパターン、端を選択すると、直径が1のパターンにうつります。
先手は、直径が1になるパターンを選択すればよいので、直径が2の際は先手の勝ちです。
直径が
の場合
直径が2の場合同様、操作後はのパターンと
のパターンにうつります。ということで、
ということで、フィボナッチ数列のDPのような感じで、入力された木の直径のパターンにおける勝敗を求めていけば、答えを求めることができます。
木の直径は、上でも挙げたこの問題の解法のように、まずはランダムな点からBFSを行い、最も遠い頂点を求め、改めてその頂点からの最長距離を求めれば、そこが直径になります。
感想
木の直径に気づきさえすれば、後は丁寧に調べていくことで解ける問題でした。はじめは、直径の偶奇に注目していましたが、それでは解けないことがわかったので、直径が小さい方から愚直に書き出していきました。
実は、木の直径がの際の勝敗は、
で割った余りを求めることで、
で求めることができるらしいです。今回はその必要がなかったですが、そこまで気づけるようにもなりたいですね。
