概要

この問題は、\(N\) 個の山から交互にカードを取り合う「不偏ゲーム（Impartial Game）」の一種です。各山から取れる枚数に制限がある場合の「ニム（Nim）」として知られており、数学的な必勝法が存在します。

考察

1. 独立したゲームの組み合わせ

このゲームは \(N\) 個の束がありますが、各プレイヤーが 1 つの束を選んで操作するため、それぞれの束は独立したゲームとみなすことができます。このようなゲームの勝敗を判定するには、グランディ数（Grundy number / Nim-value）とスプレーグ・グランディの定理（Sprague-Grundy theorem）を用いるのが一般的です。

2. 1つの束におけるグランディ数

まず、カードが \(x\) 枚ある 1 つの束だけを考えます。1 回に \(1\) 枚以上 \(K\) 枚以下のカードを取り除けるルールにおいて、この状態のグランディ数 \(g(x)\) は以下のようになります。

• \(x = 0\) のとき：動ける手がないので \(g(0) = 0\)
• \(1 \leq x \leq K\) のとき：\(0\) 枚の状態へ遷移できるため、\(g(x) = x\)
• \(x = K+1\) のとき：\(1\) 枚から \(K\) 枚の状態へ遷移できます。これらのグランディ数は \(\{1, 2, \ldots, K\}\) なので、その中に含まれない最小の非負整数（mex）は \(0\) です。よって \(g(K+1) = 0\)

この規則性を一般化すると、\(g(x) = x \pmod{K+1}\) となります。これは、周期 \(K+1\) でグランディ数が繰り返されることを意味します。

3. ゲーム全体の勝敗判定

スプレーグ・グランディの定理によれば、複数の独立したゲームを組み合わせた全体のグランディ数は、各ゲームのグランディ数の排他的論理和（XOR和）で求められます。

全体のグランディ数を \(G\) とすると： \(G = (A_1 \pmod{K+1}) \oplus (A_2 \pmod{K+1}) \oplus \cdots \oplus (A_N \pmod{K+1})\)

• \(G \neq 0\) の場合：先手（高橋君）に必勝法がある
• \(G = 0\) の場合：後手（青木君）に必勝法がある

アルゴリズム

1. 各束のカード枚数 \(A_i\) に対して、単一の束のグランディ数 \(g_i = A_i \pmod{K+1}\) を計算します。
2. すべての \(g_i\) の XOR 和（xor_sum）を計算します。
3. xor_sum が 0 でなければ Takahashi、0 であれば Aoki を出力します。

計算量

• 時間計算量: \(O(N)\)
  • \(N\) 個の要素を一度ずつ走査し、定数時間で計算可能な余りと XOR 演算を行うため、入力の数に対して線形時間で処理が終わります。
• 空間計算量: \(O(N)\)
  • 入力された \(A_i\) をリストとして保持する場合に \(O(N)\) のメモリを消費します。

実装のポイント

• 大きな入力への対応: \(N\) が \(10^5\) と大きいため、Python では sys.stdin.read().split() などを用いて高速に入力を読み込むのが効率的です。

• XOR 演算: Python では ^ 演算子を用いて XOR を計算できます。初期値 0 に対して、各要素を順に ^= で累積していきます。

  ソースコード

import sys

def main():
    # 入力を標準入力からすべて読み込む
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N: 束の数, K: 一度に取れる最大枚数
    N = int(input_data[0])
    K = int(input_data[1])
    
    # A: 各束のカード枚数
    A = list(map(int, input_data[2:]))
    
    # 各束のカード枚数に対するグランディ数（Grundy number）を計算する。
    # 1枚以上K枚以下のカードを取り除けるゲームにおいて、
    # 束の枚数が x のときのグランディ数は g(x) = x % (K + 1) となる。
    # 複数の束がある場合のゲーム全体のグランディ数は、各束のグランディ数の排他的論理和（XOR sum）である。
    
    xor_sum = 0
    mod_val = K + 1
    for x in A:
        xor_sum ^= (x % mod_val)
    
    # ゲーム全体のグランディ数が 0 であれば後手（青木君）が勝ち、
    # 0 でなければ先手（高橋君）が勝つ。
    if xor_sum != 0:
        print("Takahashi")
    else:
        print("Aoki")

if __name__ == "__main__":
    main()

---

この解説は gemini-3-flash-thinking によって生成されました。