Official

031 - VS AtCoder（★6） Editorial by Kazu1998k

公平ゲーム

このゲームについて観察してみると, 以下のことがわかる

  • 運が絡まない
  • 全ての情報が公開されている.
  • あり得る盤面の状況が有限である.
  • 一方が勝つと, もう一方は負ける.
  • 1回の操作で1つの山について, (白石の数, 青石の数) は辞書式順序の意味で真に減少している.
  • 盤面が同じならば, 操作の候補は操作をする人から影響を受けない.

この6つの条件を全て満たすようなゲームのことを公平ゲームという. この公平ゲームにおいては, 各盤面に適当な値を割り当てることで, 初期条件から先手必勝か後手必勝かが判別できる.

最小除外数

以下, \(\mathbb{N}\) で非負整数全体の集合とする. \(\mathbb{N}\) とは等しくない部分集合 \(E \subsetneq \mathbb{N}\) に対して, \(E\) の最小除外数 \({\rm mex}~E\) を \({\rm mex}~E:=\min (\mathbb{N} \setminus E)\) と定義する. 例えば,

  • \({\rm mex}~\{0,1,2,4,5\}=3\)
  • \({\rm mex}~\{0,2,3,4,5,6\}=1\)
  • \({\rm mex}~(\mathbb{N} \setminus \{0\})=0\)
  • \({\rm mex}~\emptyset=0\)

である. \({\rm mex}\) に関する性質としては以下がある. ただし, \(E \subsetneq \mathbb{N}\) とする.

\[{\rm mex}~E>0 \iff 0 \in E\]

Grundy数

公平ゲーム \(G\) におけるありうる盤面全ての集合を \(X_G\) とし, 各盤面 \(x \in X\) から遷移可能な盤面全体の集合を \(O_G(x)\) , 終点の盤面全体の集合を \(T_G\) とする. つまり, \(T_G:=\{x \in X_G \mid O_G(x)=\emptyset\}\) である.

このとき, 各盤面\(x \in X\) におけるGrundy数 \(g_G(x): X_G \to \mathbb{N}\) を

\[g_G(x):={\rm mex}~g_G(O_G(x))={\rm mex}~\{g_G(y) \in \mathbb{N} \mid y \in O_G(x) \}\]

と定義する. このように定義したGrundy数を用いて, 以下のように必勝判定できる.

公平ゲーム \(G\) において, ゲーム開始時の盤面は \(a \in X_G\) であるとする. このとき, 先手必勝であるための必要十分条件は \(g_G(a) \neq 0\) である.

ここで, 証明のために必要な事柄を以下を示す: 盤面 \(x \in X_G\) に対して, 以下が成立する. \(g_G(x) \neq 0 \iff \exists y \in O_G(x) {\rm ~s.t.~} g_G(y)=0\)

  • \(x \in X_G\) が操作不能である盤面ならば, 後手必勝であり, \(g_G(x)=0\) である.
  • \(x \in X_G\) が操作可能であり, 全ての \(y \in O_G(y)\) で成立するとする.
    • \(g_G(x)=0\) ならば, 全ての \(y \in O_G(x)\) で \(g_G(y) \neq 0\) であり, 相手が勝つことができるので, 自分は負ける. よって, 後手必勝である.
  • \(g_G(x) \neq 0\) ならば, \(g_G(y)=0\) なる \(y \in O_G(x)\) が存在する. この \(y\) を相手に渡すことにより, 仮定から相手は勝てず, 自分が勝つことになり, 先手必勝である.

この定理から公平ゲームにおける必勝判定を得ることができたが, この問題においては不十分である. 　そこで, 次にはGrundy数から新たなGrundy数を得ることを考える.

Sprague–Grundy の定理

\(G_1, \dots, G_K\) を不変ゲームとする. この \(K\) 個のゲームから以下のようなゲーム \(G\) を定義する.

  • 自分の番が来たら, \(G_1, \dots, G_K\) の中から操作が可能なゲームを1つ選び, そのゲームを \(G_i\) とする. そして, \(G_i\) のゲームに対して1回分の操作を行って相手に番を渡す.
  • 自分の番が回ってきたときに, \(K\) 個全てのゲームで操作が不能であれば自分の負けとなり, 相手の勝ちになる.

ここで, このゲーム \(G\) は公平ゲームになることが証明できる (証明は省略)

よって, \(G\) にはGrundy数を定義できるが, このGrundy数は以下のようにして表すことができる.

Sprague-Grandy

上で定義したゲーム \(G\) において, 部分ゲーム \(G_i\) の状況が \(x_i\) であるようなときの盤面を \((x_1, \dots, x_K)\) とする. このとき, \(g_G((x_1, \dots, x_K))=g_{G_1}(x_1) \oplus \dots \oplus g_{G_K}(x_K)\) が成り立つ. ただし, \(a,b \in \mathbb{N}\) に対して, \(a \oplus b\) で \(a,b\) のBitwise-Xor を表すとする.

解法

これまでの記述から, 以下のようにして先手必勝か後手必勝かどうかを判定できる.

  • \(N=1\) として, 白石と青石がそれぞれ \(w\) 個, \(b\) 個であるときの Grundy数を求める.
  • 各 \((W_i, B_i)\) に対するGrundy数 \(\gamma_i\) を求める.
  • \(\gamma_1 \oplus \dots \oplus \gamma_N=0\) かどうかを判定する.

このようにして求めると, 計算量は \((w,b)\) について, \(0 \leq w \leq W_i+\dfrac{B_i(B_i+1)}{2}, 0 \leq b \leq B_i\) の範囲を動き得ることに注意すると, \(\alpha:=\max W, \beta:=\max B\) とすると, \(O(\beta(\alpha+ \beta^2)^2+N)\) であるが, 係数が小さいことから, \(\alpha, \beta \leq 50\) の制約下では, 十分高速である.

類似問題

posted:
last update: