E - カード取りゲーム / Card Taking Game Editorial by admin
Claude 4.6 Opus (Thinking)概要
複数の束からカードを取り合う Nim(ニム)ゲームの変種です。1回に取れる枚数に上限 \(K\) がある場合の勝敗を判定します。
考察
Nim ゲームの基本
まず、取れる枚数に上限がない通常の Nim を考えます。通常の Nim では、すべての束の枚数の XOR(排他的論理和) を計算し、
- XOR \(\neq 0\) なら先手の勝ち
- XOR \(= 0\) なら後手の勝ち
というのがよく知られた定理(Sprague-Grundy の理論)です。
取れる枚数に上限 \(K\) がある場合
本問題では、1回の手番で取れる枚数が \(1\) 枚以上 \(K\) 枚以下に制限されています。このとき、各束の Grundy 数 を求めて XOR を取ればよいです。
1つの束に \(a\) 枚のカードがある場合を考えます。1回に \(1\) 〜 \(K\) 枚取れるので、これは「\(a\) 個の石から \(1\) 〜 \(K\) 個取る」という 1山の制限付き Nim と同じです。
この 1山ゲームの Grundy 数は \(a \mod (K+1)\) であることが知られています。
直感的な理由: \(K+1\) 枚のカードをひとまとまりと考えると、相手が \(x\) 枚(\(1 \leq x \leq K\))取ったら自分が \(K+1-x\) 枚取ることで、ちょうど \(K+1\) 枚を消費できます。つまり、\(K+1\) の倍数の枚数は後手必勝の「安全な位置」であり、Grundy 数は \(K+1\) で割った余りに周期的に繰り返します。
具体例
\(N = 2, K = 3, A = [5, 7]\) の場合:
- 束1:\(5 \mod (3+1) = 5 \mod 4 = 1\)
- 束2:\(7 \mod (3+1) = 7 \mod 4 = 3\)
- XOR:\(1 \oplus 3 = 2 \neq 0\) → 先手(高橋君)の勝ち
アルゴリズム
- 各束のカード枚数 \(A_i\) に対して、Grundy 数 \(A_i \mod (K+1)\) を計算する。
- 全束の Grundy 数の XOR を求める。
- XOR が \(0\) でなければ
Takahashi(先手勝ち)、\(0\) ならAoki(後手勝ち)を出力する。
N, K = map(int, input().split())
A = list(map(int, input().split()))
xor = 0
for a in A:
xor ^= a % (K + 1)
print("Takahashi" if xor != 0 else "Aoki")
計算量
- 時間計算量: \(O(N)\) — 各束について剰余と XOR を1回ずつ計算するだけ
- 空間計算量: \(O(N)\) — 配列 \(A\) の格納(XOR の計算自体は \(O(1)\) の変数で可能)
実装のポイント
\(K\) が非常に大きい(\(K \geq \max(A_i)\))場合、\(A_i \mod (K+1) = A_i\) となり、通常の Nim と一致します。これは「上限が十分大きければ制限なしと同じ」という直感とも合います。
Grundy 数の計算は
a % (K + 1)の一行で済むため、実装は非常にシンプルです。KではなくK + 1で割ることを間違えないように注意しましょう。ソースコード
N, K = map(int, input().split())
A = list(map(int, input().split()))
xor = 0
for a in A:
xor ^= a % (K + 1)
print("Takahashi" if xor != 0 else "Aoki")
この解説は claude4.6opus-thinking によって生成されました。