(より詳しい解説は後日ブログで公開します)

全体を通して「帰納法で証明できます」を省略します．

例えば \((A,B,C,D) = (0,0,0,0)\) のとき，「キャンディ \(3\) 個の皿とキャンディ \(5\) 個の皿」が場にあったらこれを「キャンディ \(6\) 個の皿」に置き換えてもよい (他の皿にかかわらずゲームの勝敗が変わらない)，というような性質があります．

大きな方針として，このような置き換えの関係によってゲームの状態を分類し，それらを非負整数などの扱いやすい値で表し，\((B,C,D)\) によって定まる「和」がどういう演算になるかを考えたいです．この方針が上手くいくかは明らかではありませんが，本問の範囲内のゲームに対応できることが以下に見るようにわかります．

\(D=0,1\) はそれぞれ normal play, misère play と呼ばれています．\((B,C)\) は複数のゲームをどう組み合わせるか (compound) を表しますが，Conway による呼び名を見出しの括弧内に記します．論文等を調べる参考にしてください．

\((B,C)=(0,0)\) (disjunctive)

\(D=0\)

Sprague–Grundy の定理としてよく知られています．ゲームの状態の nim value (Grundy 数) は，\(1\) 回の行動で nim value \(g_1, \ldots, g_k\) の状態にできるとき，\(\mathrm{mex} \{ g_1, \ldots, g_k \}\) として定まります．ゲームの和は XOR です．

\(D=1\)

このケースは一般には非常に難しいことが知られているようです．ゲーム状態に対し，misère nim value を以下で定義します：

• 行動ができないとき，\(1\)
• そうでないとき，\(1\) 回の行動で misère nim value \(g_1, \ldots, g_k\) の状態にできるとして，\(\mathrm{mex} \{ g_1, \ldots, g_k \}\)

misère nim value が \(g\) であるとは，\(A=0\) のルールでのキャンディ \(g\) 個の皿と並べると後手必勝になることと同値です．

nim value と misère nim value の組を考えます．登場しうる組が \((0,1), (1,0)\) または非負整数 \(g\) に対する \((g,g)\) のいずれかであるときに和を上手く定義できます．このようなゲームは tame と呼ばれ，本問のゲームはこの条件を満たします．

tame なゲームについて，組の和は，

• nim value は ，XOR
• misère nim value は，和をとるものすべてが \((0,1)\) または \((1,0)\) であるときは nim value と異なり，そうでない場合は nim value と等しい

によって定まります．

\((B,C)=(0,1)\) (diminished disjunctive)

\(D=0\)

操作不能な皿があったら直ちに負けです．よって \(1\) 手で操作不能にできる皿があったら勝ちです．これらがない場合，「\(1\) 手で操作不能にできる皿」を作ってはいけないというルールで \((B,C,D)=(0,0,0)\) のゲームを行うことと同じになります．

\(D=1\)

操作不能な皿があったら直ちに勝ちです．ない場合，「操作不能な皿」を作ってはいけないというルールで \((B,C,D)=(0,0,0)\) のゲームを行うことと同じになります．

\((B,C)=(1,0)\) (selective)

\(D=0\)

ゲームは結果 (手番のプレーヤーの負けか勝ちか) で \(2\) 種類に分類できます．ゲームの和は，それらすべてが負けのときに限り負けです．

\(D=1\)

操作不能な状態を除くと，\(D=0\) だと思ったときのゲームの結果と \(D=1\) だと思ったときのゲームの結果の組で \(4\) 種類に分類できます．\(2\) 個以上のゲームの和は，\(D=0\) の結果は前節の通り，\(D=1\) のときの結果は \(D=0\) の結果と同じになります．

\((B,C)=(1,1)\) (shortend selective)

操作不能な状態を除くと，\(D=0,1\) それぞれの場合で，ゲームは結果 (手番のプレーヤーの負けか勝ちか) で \(2\) 種類に分類できます．\(1\) 個以上のゲームの和は，それらすべてが負けのときに限り負けです．

\((B,C)=(2,0)\) (continued conjunctive)

勝てるならなるべく遅く勝ち，負けるならなるべく早く負けるのがよいです．ゲームはかかる手数によって分類でき，手数の偶奇と \(D\) から勝敗がわかります．ゲームの和は \(\max\) です．

\((B,C)=(2,1)\) (conjunctive)

勝てるならなるべく早く勝ち，負けるならなるべく遅く負けるのがよいです．ゲームはかかる手数によって分類でき，手数の偶奇と \(D\) から勝敗がわかります．ゲームの和は \(\min\) です．

---

あとは各 \(x\) についてキャンディ \(x\) 個の皿を表す値を計算できればよいです．多くの場合は実験でパターンを見出すこともできます．

\(A=0,1,2,3\) は統一的に扱うことができます：キャンディ \(x\) 個の皿から \(1\) 回の操作で到達できる皿のキャンディの個数は区間 \([l_x, r_x]\) で表せて，\(l_x\) や \(r_x\) はそれぞれ広義単調増加です．よって queue への push, pop および \(\mathrm{mex}\) などの計算ができるデータ構造を設計すればよいです．segment tree や C++ の std::set などで実現でき，\(X_i\) の最大値を \(X\) として \(O(X \log(X))\) 時間などで求まります．

\(A=4\) は実験・帰納法か，取り得る値の種類が少ないことを利用して計算することになります．実験で少しわかりにくいものをいくつか記しておきます：

• \((A,B,C,D)=(4,0,1,1)\)：本質的に Dawson’s Kayles というゲームと同じになります．Grundy 数が途中から周期 \(34\) をもつことが知られています．
• \((A,B,C,D)=(4,1,0,1)\)：ほぼ偶奇で決まりますが，\(\le 5\) と \(\ge 6\) で場合分けが発生します．キャンディが \(6\) 以上の偶数個あるときゲームを終了させずに奇数と奇数に分けられることが効いています．
• \((A,B,C,D)=(4,2,0,0)\)：負け状態は \(1,3,7,15,31,\ldots,2^k - 1,\ldots\) で，これらの前後で手数が増えます．
• \((A,B,C,D)=(4,2,0,1)\)：負け状態は \(2,5,11,23,47,\ldots,3 \cdot 2^k - 1,\ldots\) で，これらの前後で手数が増えます．