AtCoder ABC 067 D - Fennec VS. Snuke

D - Fennec VS. Snuke
ゲームの最善手問題です. 与えられるグラフが木構造であるというのが最大のポイントで, 閉路が存在しません. はじめに相手の色がある方へ向かって色を塗っていって相手の塗れる頂点を減らすのが最適解となります(木構造なので親を取っていれば子を相手に塗られることがないし, 先に親を取っておけば後でも子は塗れる). 1番めとN番目の最短経路を求め, 互いに距離を詰めるように塗っていき, ぬれなくなったら消化試合的に木の子を塗っていきます. これらの動作は幅優先探索で実装できます. 実装は結構面倒でした. 塗れなくなったら終わりとしてもいいですが, 何個塗れたかを数えて多かった方が勝ちとしました. 同数のときは先手が色を塗れない状態となっているので後手の勝ちです. 幅優先探索で計算量は$O(n)$でおさえられ, 間に合います.
Submission #2899733 - AtCoder Beginner Contest 067