N - Adjacent Game Editorial
by 
tatyam
全方位木 DP を用いた解法を紹介します。
このゲームを非不偏ゲームと捉えると、根付き木 (根にのみ片方のプレイヤーが印をつけることができる) に対してゲームの値が \(1\) つの超現実数として定まることがわかります。各頂点を根としたときのゲームの値を計算することができれば、この問題を解くことができます。
非不偏ゲームと超現実数
ゲームに現れる $2$ 人のプレーヤーを 左 と右 と呼ぶことにし、
- 左ができる操作が $n$ 個あり、操作 $i$ を行うとゲームの状態が $X_i$ となる
- 右ができる操作が $m$ 個あり、操作 $j$ を行うとゲームの状態が $Y_j$ となる
ようなゲームの状態を $G = \{X_1, \dots, X_n \mid Y_1, \dots, Y_m\}$ と表します。
非不偏ゲームの値は、誤解を恐れずに言えば、「何手分左が有利か？」を表す値です。
- どちらも操作を行えないゲーム $\{ \mid \}$ の値は $0$
- どちらを先手として始めても、先手が操作できずに負ける。
- ゲーム $\{\{ \mid \} \mid \}$ の値は $1$
- 右を先手として始めると、操作できず左が勝つ。
- 左を先手として始めると、左が操作を行って、ゲームの状態を $\{ \mid \}$ に変更する。その後、右が操作できず左が勝つ。
- ゲーム $\{\{ \{ \mid \} \mid \} \mid \}$ の値は $2$
- 右を先手として始めると、操作できず左が勝つ。
- 左を先手として始めると、左が操作を行って、ゲームの状態を $\{\{ \mid \} \mid \}$ に変更する。その後、右が操作できず左が勝つ。
- ゲーム $\{\mid \{ \mid \} \}$ の値は $-1$
ここで、
- ゲームの値${}>0$ $\iff$ どちらが先手になるかに関わらず左の必勝
- ゲームの値${}<0$ $\iff$ どちらが先手になるかに関わらず右の必勝
- ゲームの値${}=0$ $\iff$ ゲームが後手必勝
- ゲームの値 と $0$ が比較不能 $\iff$ ゲームが先手必勝
が成り立ちます。上の例ではゲームの値は整数でしたが、実際には、$\frac{1}{2}, -\frac{13}{8}, \ast, 1 + \ast$ などの様々な値を取り得ます。
ゲームの和
$2$ つのゲームの和 (各プレイヤーの手番では、ゲームのうち $1$ つを選んで操作を行う) の値は、$2$ つのゲームの値の和と一致します。
例えば、
- ゲーム $\{\{ \mid \} \mid \}$ の値は $1$
- ゲーム $\{ \mid \{ \mid \}\}$ の値は $-1$
- $2$ つのゲームの和 $\{\{ \mid \} \mid \{ \mid \}\}$ の値は $0$
となります。
ゲームの値の計算方法
一般の非不偏ゲームの値を計算することは難しいですが、ゲームの途中で現れるすべての状態に対して、ゲームの値が $2$ 進で有限小数となるとき、ゲームの値は簡単に計算できます。
ゲームとゲームの値を同一視することにし、値を求めたいゲームを $\{ X_1, \dots, X_n \mid Y_1, \dots, Y_m \}$ とします。
各プレイヤーは最善の選択肢を選ぶべきなので、このゲームの値は $\{ \max(X) \mid \min(Y) \}$ の値と一致します。
そこで、ゲーム $\{ X \mid Y \}$ の値の求め方を説明します。$n = 0$ なら $X = -\infty$、$m = 0$ なら $Y = \infty$ と考えます。
まず、以下の無限に続く二分木のような構造を考えます。この木には $2$ 進の有限小数がすべて現れます。
すると、ゲーム $\{X \mid Y\}$ の値は「この木の開区間 $(X, Y)$ の部分に含まれる有理数のうち、最も高い位置にあるもの」となります。
例えば、
- $\{-\infty \mid \infty\} = 0$
- $\{0 \mid \infty\} = 1$
- $\{0 \mid 1\} = \frac12$
- $\{\frac12 \mid \infty\} = 1$
- $\{-1 \mid \frac12\} = 0$
となります。
$X ≥ Y$ の場合は先手有利な成分が含まれ、ゲームの値が実数だけでは表現しきれなくなります。
非不偏ゲームと超現実数について詳しく知りたい場合は、以下をご覧ください。
https://www.ivis.co.jp/text/20111102.pdf
非不偏ゲームの問題
先手有利な成分を含む非不偏ゲームの問題
根に印を付けられるプレイヤーが左であるときの、いくつかの木に対するゲームの値を計算してみます。（根に印を付けられるプレイヤーが右であるときは、ゲームの値はこれを \(-1\) 倍したものになります。）
- 空グラフに対する値は \(\{ \mid \} = 0\) です。
- A: \(1\) 頂点の根付き木に対する値は \(\{0 \mid \} = 1\) です。
- B: 根に子が \(1\) つ繋がった \(2\) 頂点の根付き木に対する値は \(\{-1 \mid \} = 0\) です。
- 根に子が \(2\) つ繋がった \(3\) 頂点の根付き木に対する値は \(\{(-1) + (-1) \mid \} = \{-2 \mid \} = 0\) です。
- 同様に、根に子が \(x\) 個 \((x ≥ 1)\) 繋がった \(x+1\) 頂点の根付き木に対する値は \(\{-x \mid \} = 0\) です。
- 根に B が繋がった \(3\) 頂点の根付き木に対する値は \(\{0 \mid \} = 1\) です。
- 根に A と B が繋がった \(4\) 頂点の根付き木に対する値は \(\{(-1) + 0 \mid \} = \{-1 \mid \} = 0\) です。
- 根に B と B が繋がった \(5\) 頂点の根付き木に対する値は \(\{0 + 0 \mid \} = \{0 \mid \} = 1\) です。
このように、右が操作を行うことができないため、ゲームの値は \(0\) 以上であることがわかります。
また、左が \(1\) 度操作を行うと左は操作を行うことができなくなるため、左側に入るゲームの値は \(0\) 以下で、したがって、元のゲームの値は \(0\) か \(1\) のいずれかであることがわかります。
これより、根に値が \(0\) である部分木が \(x\) 個、(左が根を取れるとしたときに) 値が \(1\) である部分木が \(y\) 個繋がっているならば、ゲームの値は
\[ \{ -y \mid \} = \begin{cases} 0 & (y > 0) \\ 1 & (y = 0) \end{cases} \]
となります。
ゲームの値が正であることは、左が必勝であること (この問題では最初に操作を行うのは Alice であるので、Alice の必勝) を、\(0\) であることは、後手が必勝であること (この問題では最初に操作を行うのは Alice であるので、Bob の必勝) を表します。
したがって、全方位木 DP によって、各頂点を根としたときのゲームの値を計算することで、\(O(N)\) 時間でこの問題を解くことができます。
posted:
last update: