Grundy 数

この問題には直接関係ありませんが、比較のためにまずは Grundy 数について復習しておきましょう。次のような問題を解くのに使えるのが Grundy 数でした。

DAG があり、いくつかの頂点に駒がおかれている。(一つの頂点に複数の駒があってもよい。)
先手と後手が交互に操作を行う。自分の手番がまわってきたら、駒を一つ選び DAG の辺に沿って動かす。
動かせなくなったほうが負けのとき、どちらが勝つか？

Grundy 数の定め方

DAG の各頂点に Grundy 数とよばれる非負整数を定めます。ある頂点 \(v\) の Grundy 数は、\(v\) から出ている辺の行き先たちに割り当てられた Grundy 数を \(a_1, ..., a_k\) としたとき、\(mex(a_1, ..., a_k)\)、つまり \(a_1, ..., a_k\) の中に現れない最小の非負整数です。

勝敗判定法

各駒の置かれた頂点に対応する Grundy 数の xor が \(0\) のとき後手必勝、そうでないとき先手必勝です。

証明

ゲーム系問題の基本通り、以下の二つをチェックすればよいです。

• どの勝ち状態からも、うまく遷移を選ぶことで負け状態に遷移できる。
• 負け状態から負け状態に遷移する方法はない。

ある状態において駒が Grundy 数 \(g_1, ..., g_k\) の頂点におかれているとします。その xor を \(x\) とします。

• \(x \neq 0\) (勝ち状態) のとき、\(x\) の最高位ビットが立っているような \(g_i\) を選び、その駒を Grundy 数が \(g_i \oplus x\) であるような頂点に動かすことで (\(g_i \oplus x < g_i\) であることと Grundy 数の定義より可能)、負け状態に遷移できます。
• \(x = 0\) (負け状態) のとき、Grundy 数の定義よりどのように駒を動かしてもその駒の Grundy 数が変化し、xor も変化するので、xor は \(0\) にならず必ず勝ち状態に遷移してしまいます。

不偏ゲーム

他の問題であっても、盤面の状態を頂点、状態遷移を辺とみなすことで上に問題に帰着できる場合、Grundy 数で扱えます。ただし、状態遷移先が誰の手番かによらないという性質を用いていることに注意してください (このような問題を不偏ゲームといいます)。そうでない場合、たとえば各プレイヤーが自分の色の駒しか動かせない場合などは、別の手法が必要になります。

Partisan Game の扱い

Partisan Game (状態遷移先が誰の手番かによるゲーム) として次の問題を考えます。

DAG があり、いくつかの頂点に駒がおかれている。(一つの頂点に複数の駒があってもよい。)
また、DAG の各辺は白または黒でぬられている。
先手と後手が交互に操作を行う。自分の手番がまわってきたら、駒を一つ選び DAG の辺に沿って動かす。
ただし、先手は白の辺、後手は黒の辺しか使えない。
動かせなくなったほうが負けのとき、どちらが勝つか？

残念ながら、この問題は一般には Grundy 数の場合ほど簡単にはとけませんが、特殊な場合に効率よく解く方法を紹介します。

直感的には「自分の手番がまわってくるのが嫌なゲーム」を扱います。各頂点に実数の評価値を定めます。評価値は白に有利なほど大きく、黒に有利なほど小さくしておきます。さらに、自分の手番がまわってくるたびに嫌な思いをするように、白い辺に沿って進むと評価値が下がり、黒い辺に沿って進むと評価値が上がるようにしたいです。

評価値の定め方

ある頂点 \(v\) の評価値を DAG のトポロジカル順に以下のように定めていきます。

• \(v\) から出ている (白または黒の) 辺の行き先のうち、評価値が未定義なものが存在する場合は、\(v\) の評価値も未定義です。
• そうでないとき、\(v\) から出ている白の辺の行き先の評価値を \(a_1, ..., a_k\), 黒の辺の行き先の評価値を \(b_1, ..., b_l\) としたとき、\(v\) の評価値 \(eval(v)\) は \(\max \{ a_1, ..., a_k \} < eval(v) < \min \{ b_1, ..., b_l \}\) をみたすように定めます。
• そのような実数 \(eval(v)\) が存在しない場合、\(v\) の評価値は未定義です。
• そのような実数 \(eval(v)\) が存在する場合、(以下のルールで一意に定まります)
  • 整数にできる場合は整数にし、さらに絶対値を最小にします。
  • そうでない場合、(分母が正整数となる規約分数で書いたとき) 分母が \(2\) べきとなる有理数とし、そのうち分母が最小となるものとします。

(例)

• \(-3.125 < eval(v) < 1.5\) のとき \(eval(v) = 0\)
• \(-5.5 < eval(v) < -2\) のとき \(eval(v) = -3\)
• \(1.625 < eval(v) < 1.78125\) のとき \(eval(v) = 1.75\)

勝敗判定法

各駒の置かれた頂点に対応する評価値の和が正のとき先手必勝、\(0\) または負のとき後手必勝です。

証明

今回は、以下の二つをチェックすればよいです。

• 評価値の和が正であるとき、うまく白い辺に沿って一つ駒を動かすことで評価値の和を \(0\) または正にできる。
• 評価値の和が \(0\) または負であるとき、どのように白い辺に沿って一つ駒を動かしても評価値の和は負になる。

今は白番なので評価値の和が正かどうかに注目していますが、白の手番の後は黒番となるので評価値の和が負かどうかに注目していることに注意してください。

後者は明らかなので前者のみ示します。 現在の評価値の和を \(s\) (\(s > 0\)) とします。

• \(s\) が整数のとき 評価値の和が正であることより、評価値が正であるような頂点に置かれている駒が存在し、 そのような駒を評価値が高々 \(1\) 減少する白い辺に沿って動かすことで (評価値の定義よりつねに可能) 操作後の評価値の和を非負にできます。

• \(s\) が整数でないとき その分母を \(2^t\) とします。 このとき、評価値の分母が \(2^t\) 以上であるような頂点に置かれている駒が存在し、 そのような駒を評価値が高々 \(1/2^t\) 減少する白い辺に沿って動かすことで (評価値の定義よりつねに可能) 操作後の評価値の和を非負にできます。

この問題について

\(3^N\) 頂点の DAG を作り、\(N\) 個の駒を置きます。 DAG の頂点は一列の状態に対応します。 白い駒を進める、または黒い駒を食べることで遷移可能な状態間に白い辺をはり、黒い辺についても同様とします。 入力の各列の状態に対応する頂点に駒を一個ずつおきます。 これで、上の手法が適用できるようになりました。

評価値が未定義とならないことは証明が必要です。 DAG のトポロジカル順に帰納法で、評価値が定義できることを証明しましょう。 今頂点 \(v\) に注目していて、それよりトポロジカル順で前の頂点には評価値が定義されているとします。 このとき、白い辺 \(v \rightarrow a\) と黒い辺 \(v \rightarrow b\) があれば \(eval(a) < eval(b)\) であることを示せばよいです。

• \(v \rightarrow a\) も \(v \rightarrow b\) も「食べる」に対応する場合、\(v\) から両方食べた状態を \(c\) とすると、\(a \rightarrow c\) に黒い辺、\(c \rightarrow b\) に白い辺があり、 帰納法の仮定より \(eval(a) < eval(c) < eval(b)\) です。
• 同様に、二つの操作が互いに干渉しない場合、上のような頂点 \(c\) が存在するので同様な証明が可能です。
• \(v \rightarrow a\) が黒い駒を食べることに対応し、\(v \rightarrow b\) がその駒を進めることに対応する場合 (または白について同様の場合) だけ例外ですが、 この場合は \(b \rightarrow a\) に白い辺が存在するので \(eval(a) < eval(b)\) です。

したがって、\(3^N\) 頂点すべてについて評価値を実際に求めて和を取ることでこの問題を解くことができます。