概要

各手番で必ず石を 1 個 だけ取るゲームなので、勝敗は「全部で何手かかるか（＝石の総数の偶奇）」だけで決まります。

考察

このゲームでは、1 回の操作でできることが常に「どれか 1 山から石を 1 個取る」だけです。つまり、

• 1 手で減る石の数は必ず 1
• ゲームが終わるまでの手数は必ず \(A_1 + A_2 + \cdots + A_N\)（石の総数）

になります。途中でどの山を選ぶかによって「手数」が変わることはありません。

したがって、両者が最適に行動するといった要素は実は関係なく、

• 総手数が 奇数 なら、先手（高橋）が最後の 1 手を打つ → 高橋の勝ち
• 総手数が 偶数 なら、後手（青木）が最後の 1 手を打つ → 青木の勝ち

となります。

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

「石を 1 個ずつ取る」をそのままシミュレーションすると、最大で \(A_i \le 10^9\) なので総手数は最大 \(10^{14}\) 近くになり、当然間に合いません（TLE）。

必要なのは石の総数そのものではなく 偶奇（\(\bmod 2\)） だけです。

偶奇の計算の工夫

総和の偶奇は、各 \(A_i\) の偶奇の XOR を取れば求まります。

• \(A_1 + \cdots + A_N\) の偶奇 ＝ \((A_1 \bmod 2) \oplus \cdots \oplus (A_N \bmod 2)\)

例：\(A = [2, 5, 4]\)
偶奇は \(0 \oplus 1 \oplus 0 = 1\)（奇数）なので高橋が勝ち。
実際、総数は \(2+5+4=11\) で奇数です。

アルゴリズム

1. 変数 parity を \(0\) で初期化する。
2. 各山について \(A_i\) の下位 1 ビット（A_i & 1）を取り、parity に XOR する。
3. 最後に parity = 1 なら総数が奇数なので Takahashi、0 なら Aoki を出力する。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(1)\)

実装のポイント

• 総和を実際に計算しても Python の整数なら溢れませんが、この問題では偶奇だけ分かれば良いので x & 1 と XOR で軽く処理できます。

• 入力が大きいので sys.stdin.buffer.read() を使って高速に読み取っています。

  ソースコード

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    n = data[0]
    a = data[1:1+n]

    parity = 0
    for x in a:
        parity ^= (x & 1)

    sys.stdout.write("Takahashi\n" if parity else "Aoki\n")

if __name__ == "__main__":
    main()

---

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