😕
ABC067 D - Fennec VS. Snuke
解法
こういう木の問題は適当な頂点を根にして根付き木とすると扱いやすい
例えばフェネックの開始地点である頂点1を根として考える
すると戦略として
- フェネックはすぬけのいる部分木の頂点へ移動
- すぬけはいまいる頂点の親に移動
というのが互いにとって最善であることがわかる
まず頂点1からNまでのパスを求める
フェネックとすぬけが移動するごとに自分だけしか使えない頂点数がどれだけ増えたかを計算する(各部分木の頂点数を求めておくと高速に計算できる)
お互いが出会った地点がフェネックのターンなら(フェネックだけしか使えない頂点) > (すぬけだけしか使えない頂点)ならばフェネックの勝ち、そうでないならばすぬけの勝ち
お互いが出会った地点がすぬけのターンならば(フェネックだけしか使えない頂点) + 1 > (すぬけだけしか使えない頂点)ならばフェネックの勝ち、そうでないならばすぬけの勝ち
となる
提出コード
Discussion