概要

\(N\) 個の山から石を 1個ずつ 交互に取り、最後の石を取った人が勝つというゲームです。このゲームの勝敗は、すべての山の石の合計が「奇数か偶数か」だけで決まります。

考察

この問題のポイントは、「1回の手番で石を必ず1個だけ減らす」 というルールにあります。

1. ゲームの終了までにかかる手数

一般的な「石取りゲーム（ニム）」では、一度に複数の石を取ることができますが、本問題ではどの山を選んでも石は1個しか減りません。 そのため、ゲームが終了してすべての石がなくなるまでの 総手数 は、最初にある石の総数 \(S = A_1 + A_2 + \dots + A_N\) に等しくなります。

2. 勝敗の決まり方

1手ごとに手番が入れ替わるため、総手数 \(S\) によって勝者は以下のように確定します。 - \(S\) が奇数のとき： 1手目（高橋君）、2手目（青木君）、3手目（高橋君）… と進み、最後の \(S\) 手目は必ず 高橋君（先手） になります。 - \(S\) が偶数のとき： 同様に考えると、最後の \(S\) 手目は必ず 青木君（後手） になります。

したがって、各山の石の個数をすべて合計し、その奇偶を判定するだけで勝敗がわかります。

3. XOR和による判定の理由

提示されたコードでは、合計の代わりに「ビットごとの排他的論理和（XOR和）」を使用しています。 整数 \(a, b\) について、以下の性質があります。 $\((a + b) \pmod 2 = (a \oplus b) \pmod 2\)\( （※ \)\oplus$ は XOR 演算）

つまり、「数値の和の奇偶」と「XOR和の最下位ビット」は一致します。 今回の実装ではこの性質を利用して、全要素の XOR 和を計算し、その最下位ビットが \(1\)（奇数）か \(0\)（偶数）かを確認することで、石の総数の奇偶を判定しています。

アルゴリズム

1. 山の石の個数 \(A_1, A_2, \dots, A_N\) を読み込む。
2. 全ての要素の XOR 和（または単純な合計）を計算する。
3. 計算結果が奇数なら Takahashi、偶数なら Aoki を出力する。

計算量

• 時間計算量: \(O(N)\) \(N\) 個の要素を一度ずつ走査して計算するため、要素数に比例した時間で処理が完了します。
• 空間計算量: \(O(N)\) 入力値をすべてリストとして読み込む場合 \(O(N)\) となります。イテレータ等で逐次処理すれば \(O(1)\) まで抑えることも可能です。

実装のポイント

• 大きな数への対応: 各 \(A_i\) は最大 \(10^9\) であり、\(N\) は最大 \(10^5\) です。石の総数は最大で \(10^{14}\) 程度になるため、プログラミング言語によっては合計値が 32bit 整数型（約 \(2 \times 10^9\) まで）をオーバーフローする可能性があります。 Python では大きな整数を自動で扱えますが、他の言語では long long 型を使うか、今回のように XOR を使う、あるいは各ステップで mod 2 を取るなどの工夫が必要です。

• 効率的な入力: \(N\) が大きいため、sys.stdin.read().split() を用いて一括で読み込むことで、実行時間を短縮しています。

  ソースコード

import sys
from functools import reduce
from operator import xor

def solve():
    # 標準入力から全ての数値を取得するイテレータを作成
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # イテレータに変換して最初の要素 N を捨てる
    it = map(int, input_data)
    next(it, None)
    
    # 整数集合の和の奇偶は、その集合のビットごとの排他的論理和（XOR）の最下位ビットの奇偶と一致する。
    # この性質を利用して、全要素の XOR 和を計算する。
    # (a + b) % 2 == (a ^ b) % 2
    xor_sum = reduce(xor, it, 0)
    
    # XOR 和の最下位ビットが 1 ならば石の総数は奇数（先手勝利）、0 ならば偶数（後手勝利）
    if xor_sum & 1:
        print("Takahashi")
    else:
        print("Aoki")

if __name__ == "__main__":
    solve()

---

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