概要

各束から \(1\)～\(K\) 枚を取り除ける「複数山の取り合いゲーム」について、勝敗を Nim（ニム） の理論（グランディ数）で判定します。

考察

このゲームは「自分の手番で、どれか1つの束を選んで枚数を減らす」タイプなので、典型的な 公平ゲーム（impartial game） です。こうしたゲームは各束を独立な部分ゲームとみなし、グランディ数で合成して勝敗を決められます。

重要な気づき：1つの束は「\(K+1\) 周期」になる

1つの束だけを考えます。枚数を \(a\) とすると、次に遷移できるのは \(a-1, a-2, \ldots, a-K\)（負にならない範囲）です。

この「1回で最大 \(K\) 枚取れる」減算ゲームのグランディ数 \(g(a)\) は、実は

• \(g(0)=0\)
• \(g(a)=a \bmod (K+1)\)

になります（\(K+1\) 周期）。

理由（直感）：
\(a\) 枚からは \(1\)～\(K\) 枚減らせるので、\(a\) から到達できる状態のグランディ数は連続する \(K\) 個になります。すると最小の非負整数（mex）は周期的に \(0,1,2,\ldots,K,0,1,\ldots\) と繰り返され、結果として \(a \bmod (K+1)\) になります。

素朴なアプローチがダメな理由

• 各束の枚数 \(A_i\) は最大 \(10^9\) なので、DPで \(g(0)\) から \(g(A_i)\) まで求めると間に合いません。
• しかし上の性質により、各束は \(A_i \bmod (K+1)\) だけ見ればよい ため、高速に解けます。

勝敗判定（Nim和）

複数の束があるとき、全体の勝敗は

• \(x = g(A_1) \oplus g(A_2) \oplus \cdots \oplus g(A_N)\)（\(\oplus\) は XOR）
• \(x \neq 0\) なら先手必勝（Takahashi）
• \(x = 0\) なら後手必勝（Aoki）

で決まります。

具体例

\(N=2, K=3, (A_1,A_2)=(1,4)\) のとき
\(K+1=4\) なので - \(g(1)=1 \bmod 4=1\) - \(g(4)=4 \bmod 4=0\)

Nim和は \(1 \oplus 0 = 1 \neq 0\) より Takahashi の勝ちです。

アルゴリズム

1. \(mod = K+1\) とする
2. \(x=0\) として初期化
3. 各束について \(x \mathrel{\oplus}= A_i \bmod (K+1)\) を行う
4. 最後に \(x \neq 0\) なら Takahashi、そうでなければ Aoki を出力

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(1)\)（入力配列を保持せず逐次処理）

実装のポイント

• \(K\) や \(A_i\) が大きいので、各束は必ず \(A_i \bmod (K+1)\) に縮約してから XOR を取ります。

• \(N\) が最大 \(10^5\) なので、Pythonでは sys.stdin.buffer.read() による高速入力が安全です。

  ソースコード

import sys

def main():
    it = iter(sys.stdin.buffer.read().split())
    N = int(next(it))
    K = int(next(it))
    mod = K + 1
    x = 0
    for _ in range(N):
        a = int(next(it))
        x ^= (a % mod)
    print("Takahashi" if x != 0 else "Aoki")

if __name__ == "__main__":
    main()

---

この解説は gpt-5.2-high によって生成されました。