Official

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\) → 先手(高橋君)の勝ち

アルゴリズム

  1. 各束のカード枚数 \(A_i\) に対して、Grundy 数 \(A_i \mod (K+1)\) を計算する。
  2. 全束の Grundy 数の XOR を求める。
  3. 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 によって生成されました。