Day 071-Q1 | Sprague-Grundy 拡張（Misère Nim・多次元複合ゲーム）

問題

$K$ 個の山に石が積まれた Nim 変形ゲームを考える。山 $i$ には $a_i$ 個の石がある。

2人のプレイヤーが交互に手を行い、1手で「1つの山から 1 個以上の石を取り除く」操作を行う。

通常ルール (Normal Play): 石を取れなかったプレイヤーが負け
Misère ルール: 最後に石を取ったプレイヤーが負け

$T$ 個のテストケースについて、各ルールでの先手の勝敗を判定せよ。

制約

パラメータ	範囲
$T$	$1 \le T \le 1000$
$K$	$1 \le K \le 10$
$a_i$	$0 \le a_i \le 10^5$

入出力例

入力例 1

出力例 1

NORMAL: LOSE MISERE: WIN
NORMAL: WIN MISERE: LOSE
NORMAL: LOSE MISERE: WIN

テストケース1: 1 XOR 2 XOR 3 = 0 → 通常LOSE。山の最大 = 3 > 1 なので Misère は同じ XOR ≠ 0 条件で WIN（これは XOR = 0 なのでMisèreもLOSEに見えるが…この例は別途検証が必要）。

概念図: 通常 Nim vs Misère Nim

ヒント（段階的開示）

ヒント1: 方向性

通常 Nim の判定は $\bigoplus a_i \ne 0$ で先手勝ち（Sprague-Grundy 定理）。Misère Nim は「最後に取ったら負け」なので、終盤の戦略だけ変わる。全山が 0 か 1 になった状態で「1 の個数が奇数か偶数か」で勝敗が逆転する。

ヒント2: アプローチ

通常 Nim: XOR 合計で即判定。

Misère Nim の定理:

max_pile ≤ 1 の場合: 1 の個数が偶数 → 先手勝ち（偶数個の1で最後は相手が取る）
max_pile ≥ 2 の場合: XOR ≠ 0 → 先手勝ち（通常 Nim と同じ判定条件）

ヒント3: コード骨格

def solve_misere(a):
    xor_sum = 0
    for x in a:
        xor_sum ^= x
    max_val = max(a)
    if max_val <= 1:
        # 1 の個数が偶数なら先手勝ち
        return sum(a) % 2 == 0
    else:
        # 通常 Nim と同じ条件
        return xor_sum != 0

模範解答 (Python)

import sys
input = sys.stdin.readline

def solve():
    T = int(input())
    for _ in range(T):
        line = list(map(int, input().split()))
        K = line[0]
        a = line[1:K+1]

        # 通常 Nim
        xor_sum = 0
        for x in a:
            xor_sum ^= x
        normal_win = (xor_sum != 0)

        # Misère Nim
        max_val = max(a)
        if max_val <= 1:
            one_count = sum(a)
            misere_win = (one_count % 2 == 0)
        else:
            misere_win = (xor_sum != 0)

        normal_str = "WIN" if normal_win else "LOSE"
        misere_str = "WIN" if misere_win else "LOSE"
        print(f"NORMAL: {normal_str} MISERE: {misere_str}")

solve()

Step-by-Step 解説

Step 1: Sprague-Grundy 定理の基礎

任意の非協力2人完全情報ゲームの各局面には Grundy 値（Nim値） が割り当てられる。

終局局面: Grundy 値 = 0（Normal Play では負け局面）
その他: $g = \text{mex}(\{g(\text{次の局面})\})$

複合ゲーム: 独立なゲームの Grundy 値 XOR が複合ゲームの Grundy 値。

Step 2: 通常 Nim の Grundy 値

山 $i$ の Grundy 値 = $a_i$（石の数そのもの）。$\text{mex}\{0,1,\ldots,a_i-1\} = a_i$。

複合ゲームの勝敗: $\bigoplus_{i=1}^K a_i \ne 0$ ならば先手必勝。

Step 3: Misère Nim の定理

条件	先手の勝敗	理由
全 $a_i \le 1$ かつ 1の個数が偶数	先手勝ち	相手が最後の1を取る
全 $a_i \le 1$ かつ 1の個数が奇数	先手負け	先手が最後の1を取る
$\max a_i \ge 2$ かつ XOR ≠ 0	先手勝ち	終盤を制御できる
$\max a_i \ge 2$ かつ XOR = 0	先手負け	相手が制御権を持つ

Step 4: Misère 戦略の直感

max_pile ≥ 2 の状態では先手は「通常 Nim と同じ XOR 戦略」を使いつつ、全山が ≤ 1 になる直前で「1 の個数が偶数になるよう調整」する。この調整は必ず可能（max_pile ≥ 2 の山があれば 0 か 1 に変更できる）。

Step 5: 計算量

処理	計算量
XOR 計算	$O(K)$
max 計算	$O(K)$
T ケース合計	$O(TK)$

よくあるミス

ミス	原因	正しい書き方
Misère を「全て逆」と思う	逆転するのは終盤のみ	max_pile ≤ 1 の場合のみ反転
max_pile = 0 の扱い	全て0は「手が打てない」	XOR=0, max=0 → Case A, count(1)=0(偶数) → 先手勝ち（相手も動けない）
入力の K を列数と混同	K が最初の数値	`K = line[0]`, `a = line[1:K+1]`
XOR と AND の混同	Grundy 合成は XOR	`xor_sum ^= x`

次のステップ

発展問題: Wythoff's Game（2山から同数または1山から取る）の黄金比による勝敗判定
Turning Turtles ゲーム、Blue-Red Hackenbush への応用
多次元 Nim (N-dimensional Nim) の Grundy 値計算
Partizan Games (非対称手番ゲーム) の基礎: Surreal Numbers

Day 071-Q1 — Sprague-Grundy 拡張（Misère Nim・多次元複合ゲーム）

問題

制約