概要

この問題は、2人のプレイヤーが交互にカードを取り合うゲームにおいて、最適な行動を取った場合の勝者を判定するものです。

考察

このゲームは複数の山からなるNimゲームの一種と見なせます。ただし、各山から取れるカードの枚数は1枚以上K枚以下という制限があります。重要な観察点は、各山のカード枚数 \(A_i\) を \((K+1)\) で割った余り \(r_i = A_i \mod (K+1)\) を考えることで、通常のNimゲームに帰着できることです。

なぜ \((K+1)\) で割るのかというと、各山に対して「必敗状態」を作るためです。例えば \(K=3\) の場合、ある山の残り枚数が4枚（\((K+1)\)枚）なら、先手が何枚取っても（1～3枚）、後手が残りの枚数を全て取れるわけではなく、後手が再び1～3枚取れる状態になります。しかし、4枚という数は「どちらが取っても最終的には相手に取り切らせる」ような境界値となります。

この問題では \(K=0\) の場合に注意が必要です。この場合、プレイヤーは1枚もカードを取ることができないため、先手である高橋君は最初から行動不能となり、必ず負けます。

アルゴリズム

1. \(K=0\) の場合、高橋君は必ず負けるので “Aoki” を出力
2. それ以外の場合、各山 \(A_i\) について \(r_i = A_i \mod (K+1)\) を計算
3. すべての \(r_i\) のXOR（排他的論理和）を計算
4. XORの結果が0でなければ先手の高橋君の勝ち、0なら後手の青木君の勝ち

このアルゴリズムは、各山を \((K+1)\) で割った余りで考えることで、このゲームを通常のNimゲームと同等に扱えるという理論に基づいています。Nimゲームでは、すべての山の石の数のXOR値が0でない場合に先手が勝つことが知られています。

計算量

• 時間計算量: \(O(N)\)
  • 各山に対して定数時間で剰余計算とXOR操作を行う
• 空間計算量: \(O(N)\)
  • 入力のカード枚数を格納するための配列

実装のポイント

• \(K=0\) の場合は特別扱いする必要があります

• 大きな数値（最大 \(10^9\)）を扱うため、剰余計算は効率的に行われます

• XOR操作は累積的に行うことで、追加のメモリをほとんど使用しません

  ソースコード

def main():
    import sys
    data = sys.stdin.read().split()
    n = int(data[0])
    K = int(data[1])
    A = list(map(int, data[2:2+n]))
    
    if K == 0:
        print("Aoki")
        return
        
    xor_sum = 0
    for a in A:
        r = a % (K + 1)
        xor_sum ^= r
        
    if xor_sum != 0:
        print("Takahashi")
    else:
        print("Aoki")

if __name__ == "__main__":
    main()

この解説は deepseekv3 によって生成されました。