Grundy数を理解する

はじめに

本記事の目的は競技プログラミングにおける（不偏）ゲーム問題を解けるようになることです。具体的には以下の手順で解説します。

1. 不偏ゲームの1つであるNimを紹介し、必勝法を計算できることを示します。
2. 任意の不偏ゲームがNimと同一視できることを示します。

本記事ではビットごとの排他的論理和を知っているものとします。また、$Mex\mathrm{Mex}$というデータ構造を利用しますが、ひとこと解説があります。

対象読者

1. Grundy数が魔法だと思っている方
2. Grundy数という言葉ををはじめて聞いた方

Nim

Nimとは次のようなゲームです。

有限個のコインの山があります。2人のプレイヤーが交互に山を1つ選びコインを1つ以上とります。最後のコインをとったプレイヤーが勝ちです。

wikipediaより、引用・改変

山が1つの場合、先手必勝です。すべてのコインをとってしまえばよいからです。ところで、先手がコインを1つ以上残した場合、後手は残りのコインをすべてとることでゲームに勝利できます。このように、必勝法が存在しても最善の手を打つことができなければ負けることがあります。つまり、必勝法とは「最善の手を打ち続ければ、相手の手によらず、ゲームに勝つことができる法方」を指します。

山が2つの場合、2つの山にあるコインの枚数が同じであれば後手必勝です。最善手は、「先手が一方の山からコインをとったとき、他方の山から同じ枚数だけコインをとる」ことです（真似っこ戦略）。一方、2つの山にあるコインの枚数が異なるときは先手必勝です。初めに2つの山にあるコインの数を同じにしてから、真似っこ戦略をとれば良いからです。

山が3つの場合はどうでしょうか？　このあたりから愚直に考えるのが難しくなってきます。ところが、山が$NN$個の場合でも必勝法を計算する方法が存在します。そこで鍵になるのがGrundy数（Nim数）です。

NimのGrundy数

NimにおけるGrundy数はそれぞれの山にあるコインの数の排他的論理和で定義されます。より形式的には、$ii$番目の山にあるコインの数を$cic_i$としたときのGrundy数$gg$は

$$g=⊕i=1Nci g = \oplus_{i=1}^{N} c_i$$

です。そして$g=0g = 0$の場合は後手必勝であり、$g≠0g \neq 0$の場合は先手必勝です。急に意味が分からなくなったと思いますが、大丈夫です。Grundy数を用いて必勝法を実際に構築することで、理解できると思います。

Grundy数を用いた必勝法の構築

Grundy数にはつぎの3つの性質が成り立ちます。

1. ゲーム終了時点でGrundy数は0です。
2. Grundy数が正の時、いくつかのコインをとってGrundy数を0にする方法が存在します。
3. Grundy数が0のとき、1枚以上のコインをとるとGrundy数は正になります。

これらの性質を認めると、ゲーム開始時点でGrundy数が0の時は後手必勝で、Grundy数が正の時は先手必勝であることが分かります。必勝法の構築は自明です。つまり、（可能なら）自分の手番にGrundy数を0にすることです。そうできない場合、どう足掻いても負けです。

証明　簡便さのため、Grundy数を$gg$とかきます。

1. すべての山のコインが0枚であるとき、$g=0g=0$です。
2. $g>0g > 0$のとき、最上位ビットが存在します。これを$nn$とかくと、$ci≥2n−1c_i \ge 2^{n-1}$を満たす$ii$が（奇数個）存在します。また、$ii$番目以外の山のGrundy数は$gi=g⊕cig_i = g \oplus c_i$とかけます。このとき、$gi<2n−1g_i \lt 2^{n-1}$が成り立ちます。したがって、$ii$番目の山から有限個のコインをとることで、$ci′=gic_i' = g_i$とできます。新しいGrundy数は$g′=gi⊕ci′=0g' = g_i \oplus c_i' = 0$です。
3. $ii$番目の山からコインを1枚以上とることを考えます。$ii$番目以外の山のGrundy数は$gi=g⊕ci=cig_i = g \oplus c_i = c_i$です。$ii$番目の山からコインを1枚以上とって、$ci′c_i'$だけ残ったとします。$ci′<cic_i' \lt c_i$より、新しいGrundy数は$g′=gi⊕ci′≠0g' = g_i \oplus c_i' \neq 0$です。

以上より、必勝法を構築可能であることが分かりました。

不偏ゲーム

不偏ゲーム（公平ゲーム）とは以下の性質を満たすゲームです。

1. 2人プレイヤーの手番が交互に回ってきます。
2. 自分の手番に操作できなければ負けです。
3. 有限回の操作でゲームが終了します。
4. 盤面の状態が同じであれば、どちらの手番でも同じ操作だけが可能です。
5. プレイヤーは必要なすべての情報を持っており、操作に蓋然性はありません。

wikipediaより引用・改変

Nimのルールを思い出してみると、Nimが不偏ゲームであることが分かります。もう少し詳しく見ていきます。5つ目の要件は最善手を必ず打つために必要です。4つ目の要件は任意の不偏ゲームにおけるGrundy数の構築法（定義）と関係しています。詳細は後述しますが、同じ盤面でプレイヤーのとれる操作が異なる場合、Grundy数は破綻します^[1]。

任意の不偏ゲームにおけるGrundy数

定義（任意の不偏ゲームにおけるGrundy数）

1. ゲームの終了状態のGrundy数を0とする。
2. 任意の状態$ii$から遷移可能な状態を$SS$とする。それらのGrundy数を$g(S)g(S)$とかくと、$gi=Mex(g(S))g_i = \mathrm{Mex}(g(S))$とする。

不偏ゲームではGrundy数を矛盾なく定義できます。1回のゲームで同じ状態が2回以上現れることがなく、遷移できる状態が手番によらないからです。また、定義よりGrundy数はいくらでも小さくできます。つまりコインの枚数とほとんど同一視できます。コインと異なるのは、Grundy数を大きくできる場合があるというところだけです。

非負整数からなる任意の集合を$SS$として、$Mex(S)\mathrm{Mex}(S)$は$SS$にない最小の非負整数を表します。

任意の不偏ゲームにおける必勝法

コインの山がいくつもある場合と対応させて、いくつかの不偏ゲームを同時並行で行うことを考えます。もちろん、ただ1つの不偏ゲームを考えても良いです。このとき、Grundy数はつぎの3つの性質をもちます。

1. ゲーム終了時点でGrundy数は0です。
2. Grundy数が正の時、何らかの操作を行ってGrundy数を0にできます。
3. Grundy数が0のとき、どんな操作をしてもGrundy数は正になります。

証明　簡単のためにGrundy数を$gg$とかきます。

1. 定義より$g=0g=0$です。
2. Nimの場合と同じです。
3. Grundy数を大きくできる場合があります。$ii$番目の不偏ゲームのGrundy数を$gig_i$とかきます。また、$Gi=⊕j≠igjG_i = \oplus_{j \neq i} g_j$とします。$g=gi⊕Gi=0g = g_i \oplus G_i = 0$より、$gi=Gig_i = G_i$が成り立ちます。$ii$番目の不偏ゲームで操作を行い、Grundy数が$gi′g_i'$になったとします。このとき、$Mex\mathrm{Mex}$の定義より$gi′≠gig_i' \neq g_i$が成り立ちます。したがって、全体のGrundy数は$gi′⊕Gi≠0g_i' \oplus G_i \neq 0$です。

以上より、任意の不偏ゲームにおいてもGrundy数を用いて必勝法を構築できることが分かりました。

問題集

この問題集はChatGPTに作成してもらいました。もっと解きたい場合はAIサービスに聞いてみると良いかもしれません。また、問題内容を確認した上で、難易度順に並べ替えています。

基本問題

ヒント

Nimの章を読み直しましょう。

ヒント

実際にGrundy数を計算してみましょう。

応用問題

ヒント1

愚直にGrundy数を計算すると、計算量が$O(∣R−L∣max⁡(A))O(|R - L| \max(A))$になりTLEします。つまり、Grundy数を高速に求める必要があります。

ヒント2

Grundy数の定義を思い出しましょう。$a<la \lt l$のとき$g(a)=0g(a) = 0$です。$a>la \gt l$の場合はどうでしょうか？

ヒント3

$g(a)=0(0≤a<l)g(a) = 0 (0 \le a \lt l)$より次式を得ます。$aa$が小さいうちは$gg$が広義単調増加であることに注意してください。正式な証明は公式解説を参照してください。

$$g(a)={00≤a<lg(a−l)+1l≤a<a+r g(a) = \begin{cases} 0 & 0 \le a \lt l \\ g(a-l) + 1 & l \le a \lt a+r \end{cases}$$

$a≥l+ra \ge l+r$の場合はどうでしょうか？　$Mex\mathrm{Mex}$の定義をよく思い出してください。$l≪r≪al \ll r \ll a$のGrundy数を（愚直に）シミュレートするのも1つの手です。

また、$gg$を再帰的に実装すると$a/la/l$が大きい場合にTLEしてしまいます。

解けたら読んでください

AtCoderProblemsによると、この問題の難易度は青色相当です。解けたあなたは結構すごいです。

数学的な問題もそうですが、Grundy数を計算する問題はスコアが高めに設定されているように思います。この手の問題が出題されることは少ないのですが、「Grundy数を計算できる」ようになると解けるようになります。青色問題は現在の環境ではF問題相当です。5冠や6冠も夢ではありません。

最善手を計算する問題です。集大成として、取り組んでみてください。

ヒント1

まずは愚直にGrundy数を計算してみましょう。どのように定義できますか？

ヒント2

連続する要素の数を$ii$とおくと、Grundy数は次のようにかけます。

$$gi=Mex({gx⊕gy∣L≤i−x+y≤R}) g_i = \mathrm{Mex}(\{ g_x \oplus g_y | L \le i - x + y \le R \})$$

計算量は$O(N3)O(N^3)$です。どのようにして高速化しますか？

ヒント3

「連続する要素」は区間とみなすことができます。ヒント2からもわかるように、この問題は区間の分轄の一種です。区間に関わる問題では差分計算が有効な気がします^[2]。累積和やいもす法、Moのアルゴリズムも差分計算です。

追加問題

1. https://atcoder.jp/contests/abc206/tasks/abc206_f
2. https://atcoder.jp/contests/arc091/tasks/arc091_d

おわりに

本記事を通じて、ゲーム問題に自信を持って回答できる方が増えれば幸いです。また、誤っている点や不足している点があればコメントでお知らせください。

更新履歴

2025-03-17: 誤字修正
2025-03-18: 問題の差し替え

脚注

1. 他によい指標がないとは言っていません。あるとも言っていません

2. 経験則です。「区間の中身をすべて考慮する必要があるので、計算済みの値を利用する」と考えると納得できるかもしれません。