二人零和有限確定完全情報ゲーム

二人零和有限確定完全情報ゲームで、かつ、グランディー数が関係しないものを解析する。今の所、過去問並べただけ。

後退解析

遷移が有向グラフ \(G\) で表されるゲームの勝敗は \(v \in V(G)\) について

\(v\) が負けのとき、\(v\) に遷移可能な頂点 \(\delta^-(v)\) は勝ち
\(v\) から遷移可能な頂点 \(\delta^+(v)\) が全て勝ちのとき、\(v\) は負け

である。ゲームの終了条件が決められている頂点から順に決定すればよい。勝敗の確定しなかった頂点は、勝敗の確定しなかった頂点に遷移するのが最適である。従って、永遠に勝敗が決まらない。将棋ではこのような状態を避けるため、同一局面が4回現れると引き分けとする、千日手が設定されている。

DAGの後退解析

DAGの場合、後退解析は簡略化できる。閉路が存在しないので、勝敗が決まらない頂点は存在しない。

ゲームの終了状態に、勝敗を割り振る。
勝敗が未確定の頂点を、一時的に、負け状態と仮定する。
トポロジカル順序の逆順に頂点 \(v\) を見る。
\(v\) が勝ちなら何もしない。\(v\) が負けなら、\(v\) に遷移可能な頂点を勝ちにする。

トポロジカル順序が自明ならば、手で勝敗が簡単に書き下せる場合がある。

問題1:石が \(N\) 個ある。交互に \(1\) 個以上 \(K\) 個以下の石を取り去る。石が取れなくなった方が負け。どちらが勝つか。\(O(1)\)で求めよ。（有名問題、yukicoder 8）

DAGの後退解析をすればよい。先手の敗北条件は \(N = 0 \pmod {K+1} \) である。

問題2:問題1において、取り去ったあとの石の個数が \(x_1, x_2, \ldots, x_M\) のいずれかになる操作が禁止されたとするとする。勝敗を \(O(M)\) で求めよ。（yukicoder 1313）

DAGの後退解析。

問題3:問題1において、相手が直前に取り除いた石と同数の石が取り除けない場合の勝敗を \(O(N)\) で求めよ。（yukicoder 1770）

DAGの後退解析。「直前に相手が \(x\) 個取り除いてなければ」勝ちという条件を論理和で配るので、各頂点の状態は

直前に相手が何個取り除いていようが、負け
直前に相手が \(x\) 個取り除いていれば、負け
直前に相手が何個取り除いていようが、勝ち

のいずれか。１つ目の状態が最短でも K+1 個おきにしか起きないので、更新回数は全体で \(O(N)\) になる。

問題4:問題2,3を合わせた場合について解け

解答略

問題5:問題1において、取り去ったあとの石の個数が2進表記したとき 1 が奇数個となる操作が禁止されたとするとする。勝敗を \(O(N)\) で求めよ。（SRM 701 Div2 Hard）

DAGの後退解析。問題2の類題。

問題6:有向グラフ G の各頂点には数字が書いてある。頂点 1 に駒を置き、交互に

駒を辺に沿って動かす。
ゲームを終了する。

のどちらかを選ぶ。十分長いターンが経ってもまだゲームが終了していないときは、強制終了する。ゲームが終了したときに、駒が置いてある頂点の数字（スコア）を先手は最大化、後手は最小化したい。数字はいくつになるか。（ARC038D）

スコアについて二分探索すると後退解析になる。

問題11:
いくつかの根付き木が与えられる。交互に次のいずれかの操作を繰り返す。

1ターン目ならば駒を好きな木の根に置く。
葉でなければ、駒を子に移動する
葉であれば、まだ選ばれていない木の根に駒を移動する

操作できなくなったほうが負け。どちらが勝つか。
（Kupc2019E）

木の根を選び、葉まで駒を動かしてから、次の根を選ぶのが先手後手のどちらになっているか考える。

先手の意思で、先手後手を入れ替えることができる
先手の意思で、先手後手をそのままにすることができる

(True, True) を選ぶと先手の勝ち。(False, False) を選ぶと後手の勝ち。従って (False, False) が選ばれるのは最後。(True, False) ならば先手後手は必ず入れ替わる。(False, True) ならば先手後手は必ずそのまま。従って、(False, True) は勝敗と無関係。

勝敗の単調性

あるパラメータ A が大きいほど先手が有利（或いは不利）ならば、

\(f_1(S, a) :=\) 状態 S でパラメータ A = a のときの勝敗

を持つ dp から

\(f_2(S) :=\) 状態 S のとき、先手が勝つための A の最小値

を持つ dp に変更でき、状態数が減らせる。

問題13:
N 個の石が相異なる非負整数座標 \(x_1, x_2, \ldots, x_N\) (\(0 < x_1 \leq \cdots < x_N\)) に置かれている。交互に、最も大きい座標に置かれている石を、他の石と重ならないように、より小さい非負整数座標に置き換える。操作できなくなったほうが負け。どちらが勝つか。
(ARC137C)

単調性より、\(x_N\) が大きいほど先手が有利。戦略盗みにより、\(x_N-x_{N-1} \geq 2\) ならば先手の勝ち。さもなくば、\(x_N-x_{N-1} =1\) を保ちながら遷移するしかないので、最適手は \(O(N)\) でシミュレートできる。

問題14:木の根以外の頂点に得点が書き込まれている。駒が根においてある。次の手順をゲーム終了まで繰り返す。

先手は好きな頂点を1つ選び書き込まれた数字を零にする。
後手は子に駒を移動する。葉に移動した場合はゲーム終了。葉でもなくとも、後手の意思で終了にできる。

ゲーム終了時点で駒がある頂点に書き込まれた数字が得点になる。先手は得点を最小化、後手は得点を最大化したい。何点になるか。(ABC246G)

得点はX点以上か？について二分探索して、後退解析。取り除ける頂点が多いほど先手は有利なので、dp[v] := (頂点 v の部分木でゲームをしたとき得点を X 未満にするには、予め何個の頂点の得点を零にしておく必要があるか) について dp ができる。

問題12:
\(a_1, a_2, \ldots, a_N\) 個の石からなる山が \(N\) 個ある。Aさんは右端の山から好きな個数の石を取ることができ、Bさんは左端の山から好きな個数の石を取ることができる。交互に操作を行う。操作できなくなったほうが負け。どちらが勝つか。
(AGC048D)

指せる手の単調性より

\(a_1\) が大きいほど A さんが有利
\(a_N\) が大きいほど B さんが有利

だから、操作は

山から石を一つだけ取る
山から石を全て取る

のどちらかであるとしても勝敗は変化しない。

残っている山が \(l, \ldots, r\) 番目で、\(l\) 番目の山以外は初期状態と石の個数が同じである。A さん先手で、A さんの勝ちとなる \(a_l\) の最小値 \(f(l, r)\)
残っている山が \(l, \ldots, r\) 番目で、\(r\) 番目の山以外は初期状態と石の個数が同じである。B さん先手で、B さんの勝ちとなる \(a_r\) の最小値 \(g(l, r)\)

\(f(l, r-1), g(l+1, r)\) から \(f(l, r), g(l, r)\) が \(O(1)\) で求まる。

不変量に着目する

二部グラフ

二部グラフ上のゲームの場合、各部集合が何らかの不変量と関連していることが多い。特に、グリッドグラフが頻出である。

問題8:H 行 W 列のマスがある。N 個の駒を \((x_i, y_i)\) \((1 \leq i \leq N)\) に置いた。交互に駒を一つ選んで一つ左か下に動かすことを繰り返す。同じマスに複数の駒をおいてはいけない。操作ができなくなったほうが負け。どちらが勝つか。（yukicoder2951）

H = 1 の場合を考える。N = 1 のときは先手必勝。N = 2 のときは、

(x+y) mod 2 = 0 に置かれた駒の個数 A
(x+y) mod 2 = 1 に置かれた駒の個数 B

について、\(A \neq B \Leftrightarrow \) 先手必勝。一般の N について、(A, B) は、駒を動かすたびに (-1, 1), (1, -1), (-1, 0), (0, -1) の何れかが足される。A-B には、-2, 2, -1, 1 が足される。従って、\(A – B \neq 0 \pmod 3 \Leftrightarrow \) 先手必勝が予想される。実際に正しいことが証明できる。

問題15:グリッドグラフの部分グラフと、非隣接な頂点 s, t が与えられる。交互にグラフの頂点を削除する。自分の操作で頂点 s, t を非連結にした方が勝ち。先手と後手のどちらが勝つか。(UTPC2021L)

s, t の点連結度が1のとき先手の勝ち。
s, t の点連結度が2のとき、点連結度を1にしたほうが負けなので、その直前では、2つの内素な s-t パスだけになる。二部グラフなので、このときの頂点数はそれまでの操作によらない。従って勝敗も O(1) で分かる。

偶奇

偶奇が不変量に関連していることがある。

問題7:正整数列が与えられる。次のどちらかの操作を交互に行う。

すべての要素を 1 減らす。全ての要素が正整数である場合のみこの操作ができる。
正整数を一つ選び、1 減らす。

操作ができなくなった方が負け。どちらが勝つか O(1) で求めよ。

（KUPC2020春E）

（最小値、総和）の偶奇の遷移は下図のようになる。\(N\) の偶奇によらず二部グラフになる。最小値 0 だと、全要素を 1 減らす遷移ができないが、可能な遷移は部分グラフであるので、なお二部グラフである。

問題9:全要素の gcd が 1 であるような数列 A がある。交互に2以上の要素を選んで 1 減らしたあとに、全体を gcd(A) で割ることを繰り返す。操作できなくなったほうが負け。どちらが勝つか。（AGC010D）

gcd で割らなければ、\(\sum (A_i – 1)\) 回操作ができる。gcd は常に奇数なので、\(A_i, A_i/\mathrm{gcd}(A)\) の偶奇は同じ。従って、\(\sum (A_i – 1) = 1 \pmod 2 \Leftrightarrow\) 先手の勝ち。

問題10:それぞれ、\(a_i\) 個の石（\(1 \leq i \leq N\)）からなる山がある。先手と後手は交互に次のどちらかの操作をする。

山を２つに分割する。
各山から石を一つ取り除く。ただし、各山に2つ以上の石がなくてはならない。

操作できなくなったほうが負け。どちらが勝つか。（出典 : yukicoder1852）

(i) : \(\min(a)=1\) のとき、 \(S := \sum (a_i-1)=1 \Leftrightarrow \) 先手の勝ち。
(ii) : \(\min(a) > 1\) のとき、\(a_1\) を \(1, a_1-1\) に分割すると、(i) の \(S \leftarrow S-1\) の場合に帰着される。従って、\(S\) が奇数なら先手の勝ち。さもなくば、\(\forall i, a_i \leftarrow a_i-1\) の操作しか先手はできず、後手に \(S \leftarrow S-N\) の状態で渡される。\(N\) が奇数なら、先手の負け。\(N\) が偶数なら、\(\min(a)\) の偶奇で勝敗が決する。

問題16:
グラフGが与えられる。交互に辺を追加する。連結になった方が負け。どちらが勝つか。
(AOJ2376)

連結になる直前の連結成分の大きさが k, n-k とすると、追加された辺の本数は n(n-1)/2-|E|-k(n-k) である。n が奇数ならば、連結成分は偶数と奇数の大きさが一つずつなので、 n(n-1)/2-|E| = 0 mod 2 ⇔ 先手勝利　である。

偶サイズの連結成分の個数
奇サイズの連結成分の個数
連結成分の個数を変えずに追加できる辺の個数の偶奇

偶と偶をマージ (-1, 0, 1)
偶と奇をマージ (-1, 0, 1)
奇と奇をマージ (1, -2, 0)
連結成分内で辺を追加 (0, 0, 1)
これより、(0, 0, 0) のほうが (1, 1, 0)より作りにくそうに見える。奇成分は常に偶数個あるから、実際、偶数が一つでもある状態で回ってこれば、偶数が2つ以上にして相手に渡せる。他のケースはこれを元に理詰め。