AtCoder Regular Contest 143 の C 問題の解説の行間を埋める

話題とする問題はこちら。 atcoder.jp

ゲームってことは xor？と思いきや、不偏ゲームは両プレイヤーの操作が同じ場合の話なので、今回のようなケースだと解けません。
もしかしたら適切にアドホックな改修を加えれば解けるのかもしれませんが。

カテゴリ的には「二人零和有限確定完全情報ゲーム」らしく、(手番プレイヤー, 状態)を節、遷移を辺として、グラフを構築し、トポロジカルソートして終了手番の方から埋めていけば勝敗を判定することができます。

計算量としては、今回の問題ですと $O(\max(A_{i})^{N})$ です。
制約は $1 \leq A_{i} \leq 10^{9}, 1 \leq N \leq 2 \times 10^{5}$ なので、さすがに2秒は間に合いません。

解説を見た感じ、

必敗盤面となる特定の盤面を列挙する。
- ここで列挙される必敗盤面は、 $X$ と $Y$ の大小に依存しない。
先手手番で、後手に ↑ の必敗盤面を押し付けることのできる盤面を列挙する。これは、必勝盤面となる。
- 条件として $X \leq Y$ が要求される。
- この時点で、 $X \leq Y$ における初期盤面を必勝盤面と必敗盤面に分類できたことになる。
のときに、適切な操作をすれば相手に必敗盤面を押し付けられる盤面を必勝盤面、どのような操作をしても相手に必勝盤面が渡ってしまう盤面を必敗盤面とする。
- 相手に渡した盤面が必勝盤面か、必敗盤面かは $X \leq Y$ における初期盤面が分類済みなので即座に判定可能。