アルゴリズム忘備録

競技プログラミングとかデータ分析とか

D: Fennec VS. Snuke - AtCoder Regular Contest 078

arc078.contest.atcoder.jp

 

木が与えられる。頂点のうち、1点は白、もう1点は黒、残りは色なしの状態である。先手は白に塗られた頂点から隣接する頂点にだけ、後手は同様に黒の頂点だけ色を塗っていくことが可能である。ただし、既に塗られたところには上塗り出来ない。交互に手番がきて操作ができなくなったほうが負けのとき、勝つのはどちらか?

 

木なので、最適戦略はなるべく自分しか塗れない領域を増やすことだとわかる。そこで、まず最初の白の頂点と黒の頂点について最短パスを求めよう。この最短パスの長さが偶数、及び奇数の場合について場合分けし、それぞれが塗ることが可能な最大距離を求める。あるところで最短パスの中で白と黒の頂点の境目ができるが、ここで木を分離し、二つの木を作る。するとこの木は白及び黒が塗ることができる最大手数になっている。あとはこれをdfsなりでカウントすればよい。O(N)。