Day 163-Q1 | Moore の Nim

問題

石の山が $N$ 個あり、山 $i$ には $a_i$ 個の石がある。先手と後手が交互に次の操作を行う。

空でない山を 1 個以上 $k$ 個以下 選び、選んだ各山から 1 個以上の石を取り除く（山ごとに取る個数は違ってよい）

操作できなくなった（すべての山が空になった）人の負けである。$T$ 個のテストケースそれぞれについて、双方が最善を尽くしたとき先手が勝つなら First、後手が勝つなら Second を出力せよ。

入力形式

T
N_1 k_1
a_1 a_2 ... a_{N_1}
...
N_T k_T
a_1 a_2 ... a_{N_T}

制約

#	条件
1	$1\le T\le 10^5$
2	$1\le N_j\le 2\times10^5$、$\sum N_j\le 2\times10^5$
3	$1\le k_j\le N_j$
4	$0\le a_i\le 10^{18}$
5	入力はすべて整数

入出力例

入力例1

出力例1

Second
First
Second

（1 件目: 3 山から同時に取れるのは 2 山まで。どう取っても相手が残りを取り切れる。XOR は $1\oplus1\oplus1=1\ne0$ なので、通常の Nim の判定だと First と誤答する）
（2 件目: $k=2\ge N$ なので両方の山を一度に空にできる。XOR は $5\oplus5=0$ なので、通常の Nim の判定だと Second と誤答する）
（3 件目: $k=1$ は通常の Nim。$1\oplus2\oplus3=0$ で後手必勝）

背景と出典

E. H. Moore, "A Generalization of the Game Called Nim", *Annals of Mathematics* 11(3), 1910, pp. 93–94 が初出で、"Moore's Nim" や "Nim$_k$" と呼ばれる。Berlekamp–Conway–Guy『Winning Ways』にも載る古典。本セッションでは原論文を開いておらず、正しさの根拠は下の検証ログ（全局面探索 2930 局面との照合）と Step 3・4 の証明である。

AtCoder では「1 山だけ動かす Nim の変形」が多く、複数の山を同時に動かせる型は Grundy 数の XOR が使えない（ゲームが「独立な山の和」ではなくなる）。そこが本問の要点。

概念図：ビットごとの 1 の個数

ヒント（クリックで段階的に開示）

ヒント1（方向性）

山が独立でないので、Grundy 数の XOR は使えない。まず小さい局面を全探索して、後手必勝の局面を眺めよう。$k=1$ のときの「XOR が 0」を、ビットごとの言葉で言い直すとどうなるか。

ヒント2（アプローチ）

「XOR が 0」⇔「どのビット位置でも、そのビットが 1 の山が 偶数（= 2 の倍数） 個」。
$k$ 山まで同時に動かせるなら、「どのビット位置でも、そのビットが 1 の山が $k+1$ の倍数 個」が後手必勝の局面になると予想できる。

ヒント3（誘導）

証明は 2 方向。

その局面からどう動かしても条件が崩れる: 動かした山のうち、値が変わった最上位ビット $b$ に注目。ビット $b$ では、変わった山はすべて $1\to0$ になっている
条件が崩れた局面からは、条件に戻す手がある: 上のビットから順に、「すでに減らした山（下位ビットを自由に決められる）」を使い回しながら個数を $k+1$ の倍数にそろえる

模範解答 (Python)

模範解答を表示する（まず自力で解いてから）

import sys


def main():
    data = sys.stdin.buffer.read().split()
    t = int(data[0])
    p = 1
    out = []
    for _ in range(t):
        n, k = int(data[p]), int(data[p + 1])
        p += 2
        cnt = [0] * 60                      # cnt[b] = ビット b が 1 の山の個数（a_i <= 10^18 < 2^60）
        for x in data[p:p + n]:
            x = int(x)
            b = 0
            while x:
                if x & 1:
                    cnt[b] += 1
                x >>= 1
                b += 1
        p += n
        # すべてのビットで 1 の個数が k+1 の倍数なら後手必勝
        out.append("Second" if all(c % (k + 1) == 0 for c in cnt) else "First")
    print("\n".join(out))


main()

計算量: $O(\sum N_j\cdot\log\max a)$。実測（Python 3.14.7、M1 Mac）で $N=2\times10^5$、$a_i<10^{18}$ の乱数、$k=3$ が 0.89 s。

Step-by-Step 解説

1なぜ Grundy 数の XOR が使えないか

Sprague–Grundy の定理は「各手番で ちょうど 1 つ の成分だけを動かす」ゲームの和についての定理。本問は 1 手で最大 $k$ 山を動かすので、山を独立な成分とみなせない。実際、全山の Grundy 数（= $a_i$）の XOR で判定すると全 2930 局面中 332 局面で勝敗を誤る（実測、検証ログ）。

2予想を立てる

$N\le4$、$a_i\le4$ の全局面を全探索すると、後手必勝の局面はちょうど「各ビット位置で 1 の個数が $k+1$ の倍数」のものだった。$k=1$ なら「偶数」＝XOR が 0 で、通常の Nim と一致する。以下、この条件を満たす局面の集合を $\mathcal P$ と書く。

3$\mathcal P$ からどう動かしても $\mathcal P$ の外に出る

1 手で値が変わる山は 1〜$k$ 個で、どれも値が減る。変わった山すべてを通して、値が変わるビットのうち最上位を $b$ とする。
ある山がビット $b$ で変わったなら、$b$ はその山にとっても「変わる最上位ビット」なので、値が減る以上 $1\to0$ でなければならない。よってビット $b$ の 1 の個数は $c$（$1\le c\le k$）だけ減る。$k+1$ の倍数から $1\sim k$ を引くと $k+1$ の倍数ではない。

4$\mathcal P$ の外からは $\mathcal P$ に入れる（勝ち手の作り方）

上のビットから順に見る。これまでに「選んだ山」の集合を $C$（最初は空）とする。選んだ山はすでに上位ビットで $1\to0$ にしているので、それより下のビットは自由に決めてよい（決めた値は元より小さい）。

ビット $b$ で、$C$ に入っていない山のうちビット $b$ が 1 のものの個数を $u$、$r=u\bmod(k+1)$、$m=|C|$ とする。

$m+r\le k$ なら: ビットが 1 の未選択の山から $r$ 個を選んで $C$ に加え、そのビットを 0 にする。$C$ の山のビット $b$ はすべて 0 にする。1 の個数は $u-r$ で $k+1$ の倍数
$m+r>k$ なら: $m\ge k+1-r$ なので、$C$ の山のうち $k+1-r$ 個のビット $b$ を 1、残りを 0 にする。1 の個数は $u+(k+1-r)$ で $k+1$ の倍数

どちらも $|C|\le k$ を保つ。$\mathcal P$ の外ならどこかのビットで $r\ge1$ となり $C$ が空でなくなるので、「1 山以上」を動かす正しい手になる。

5実装

各ビットの 1 の個数を数え、すべて $k+1$ で割り切れるかを見るだけ。$k\ge N$ なら個数は高々 $N<k+1$ なので「全部 0」のときだけ後手必勝（＝全部取れる）となり、直感とも合う。

迷った他案と採らなかった理由

案	計算量	採否	理由
通常の Nim と同じ XOR 判定	$O(N)$	不採用	全 2930 局面中 332 局面で誤り（実測）。入力例 1 の 1・2 件目がその例
石の総数 $\bmod (k+1)$ で判定	$O(N)$	不採用	「1 山から $k$ 個まで取る」石取りゲームと混同した判定。807 局面で誤り（実測）
局面の状態 DP（全探索）	状態数 $\prod(a_i+1)$	検算用のみ	$a_i\le4$・$N\le4$ で 625 状態が限界。検算には使った
各山の Grundy 数を求めて XOR	—	不採用	山が独立でないので定理の前提を満たさない（Step 1）
ビットごとの個数 $\bmod(k+1)$（本解）	$O(N\log\max a)$	採用	全局面探索と 2930 局面で全件一致、証明あり（Step 3・4）

前提が変わったら:

最後に取った人が負け（misère） なら結論が変わる。通常の Nim の misère は「全山が 1 以下なら偶奇が逆転」の補正で済むが、Nim$_k$ の misère は本問の範囲外（検証していない）
「ちょうど $k$ 山」を動かす ルールなら別ゲーム。本問の証明の Step 4 は「$k$ 山以下」を使っている
勝ち手も出力 するなら Step 4 をそのまま実装する（$O(N\log\max a)$）。発展問題 1

よくあるミス

ミス	原因	正しい書き方
XOR で判定する	$k=1$ の結論をそのまま流用	ビットごとの 1 の個数を $k+1$ で割る（332 局面で誤り）
総数 $\bmod(k+1)$ で判定する	「1 山から $k$ 個まで取る」ゲームと混同	取る山の数が $k$ まで、個数は自由（807 局面で誤り）
ビット数を 30 で打ち切る	$a_i\le10^9$ の癖	$10^{18}<2^{60}$ なので 60 ビット
`bin(x).count` をビットごとに回す	1 ビットずつの抽出を 60 回×$N$ 回	1 数ずつ下位ビットから数えれば 1 回の走査で済む

次のステップ

発展1: 先手必勝のとき、勝ち手を 1 つ出力する（Step 4 の構成をそのまま実装。全探索と照合して確かめる）
発展2: 「$k$ 山まで、ただし各山から取れるのは $L$ 個まで」のように取る個数も制限すると、各山を $a_i\bmod(L+1)$ に置き換えてよいかを証明つきで確かめる
次回予告: 焦点帯 M1 を続ける（DP・ゲーム）

検証ログ（本セッションで実行した数値）

全局面探索との一致（実測）: $N=1..4$、$k=1..N$、$a_i\in\{0,..,4\}$ の全 2930 局面で、状態 DP（メモ化再帰で全手を列挙）の勝敗とビット判定が全件一致。プログラム全体（標準入出力に 2930 テストケースを 1 度に流す）でも 0 件の不一致
誤った判定の誤り数（実測）: 全 2930 局面中、XOR 判定 332 局面・総数 $\bmod(k+1)$ 判定 807 局面
実行時間（実測）: $N=2\times10^5$、$a_i\in[0,10^{18}]$ の乱数、$k=3$ で 0.89 s（出力 First）
扱っていない範囲: misère 版、勝ち手の出力（Step 4 は証明のみで実装・照合していない）、Moore の原論文との照合

自己評価

完全理解おおむね理解要復習

Day 163-Q1 — 2026-09-28 — Moore の Nim_k（一度に k 山まで取れる Nim。各ビットの 1 の個数が k+1 の倍数なら後手必勝）

問題