概要

\(N\) 個の石の山から交互に石を1個ずつ取り、最後の石を取った方が勝ちというゲームです。全体の石の合計が奇数なら先手（高橋君）、偶数なら後手（青木君）が勝ちます。

考察

重要な気づき：このゲームには戦略の余地がない

一見すると「どの山から取るか」の選択が重要に見えますが、実はどの山から取っても結果は変わりません。

その理由を考えてみましょう：

• 毎ターン、必ずちょうど1個の石が取り除かれます。
• 石が残っている限り、手番のプレイヤーは必ず石を取らなければなりません（パスはできません）。
• すべての石がなくなったらゲーム終了です。

つまり、ゲームは必ず合計 \(S = A_1 + A_2 + \cdots + A_N\) ターンで終了します。どの山から取るかに関係なく、全部で \(S\) 回の操作が行われます。

具体例

• 例1: 石が \([3]\)（合計 \(3\)）の場合 → 3ターンで終了。1, 3ターン目は先手、2ターン目は後手。最後（3ターン目）は先手 → 高橋君の勝ち
• 例2: 石が \([2, 2]\)（合計 \(4\)）の場合 → 4ターンで終了。最後（4ターン目）は後手 → 青木君の勝ち
• 例3: 石が \([1, 2]\)（合計 \(3\)）の場合 → 3ターンで終了。最後は先手 → 高橋君の勝ち

結論

• \(S\) が奇数のとき：最後の石を取るのは先手（高橋君）→ 高橋君の勝ち
• \(S\) が偶数のとき：最後の石を取るのは後手（青木君）→ 青木君の勝ち

「どの山から取るか」という選択は結果に影響しないため、石の合計の偶奇だけで勝敗が決まります。

アルゴリズム

1. \(N\) 個の山の石の数 \(A_1, A_2, \ldots, A_N\) を読み込む。
2. 合計 \(S = A_1 + A_2 + \cdots + A_N\) を計算する。
3. \(S\) が奇数なら Takahashi、偶数なら Aoki を出力する。

計算量

• 時間計算量: \(O(N)\)（配列の合計を求めるだけ）
• 空間計算量: \(O(N)\)（配列の格納に必要）

実装のポイント

• \(A_i\) は最大 \(10^9\)、\(N\) は最大 \(10^5\) なので、合計 \(S\) は最大 \(10^{14}\) 程度になります。Python では整数のオーバーフローを気にする必要はありませんが、C++ などでは long long を使う必要があります。

• 実は合計そのものを求めなくても、各 \(A_i\) の偶奇だけに注目して「奇数の個数」が奇数か偶数かで判定することも可能です（奇数が奇数個あれば合計は奇数）。ただし、sum を使う方がシンプルです。

  ソースコード

N = int(input())
A = list(map(int, input().split()))
total = sum(A)
if total % 2 == 1:
    print("Takahashi")
else:
    print("Aoki")

---

この解説は claude4.6opus-thinking によって生成されました。