概要

石取りゲームにおいて、両者が最適に行動したときに勝つプレイヤーを判定する問題です。

考察

このゲームは「最後の石を取ったプレイヤーが勝ち」というルールです。各山から石を1つずつ取り除く操作を交互に行うため、ゲーム全体で行われる操作回数は全ての山の石の数の合計 \(total = \sum_{i=1}^{N} A_i\) 回になります。

重要な観察は、ゲームの勝敗が操作回数の偶奇だけで決まることです。操作回数が奇数なら先手（高橋君）の勝ち、偶数なら後手（青木君）の勝ちになります。なぜなら、各操作は石を1つ取り除くだけなので、ゲームの進行に選択の余地がなく、両者が最適にプレイしても操作回数は常に同じになるからです。

アルゴリズム

1. 全ての山の石の個数の合計 \(total\) を計算する
2. \(total\) が奇数か偶数かを判定する
3. 奇数なら先手の「Takahashi」、偶数なら後手の「Aoki」を出力する

計算量

• 時間計算量: \(O(N)\)
  • 石の個数の合計を計算するために、\(N\) 個の要素を走査する
• 空間計算量: \(O(N)\)
  • 入力された石の個数を格納するための配列が必要

実装のポイント

• 入力の読み取りは sys.stdin.read() を使って効率的に行う

• 石の個数の合計は組み込み関数 sum() を使って計算する

• 偶奇判定は剰余演算 % 2 で行う

• 大きな数値（最大 \(10^5 \times 10^9 = 10^{14}\)）を扱うが、Pythonの整数型は自動で多倍長整数を扱えるため問題ない

  ソースコード

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    n = int(data[0])
    A = list(map(int, data[1:1+n]))
    
    total = sum(A)
    if total % 2 == 1:
        print("Takahashi")
    else:
        print("Aoki")

if __name__ == "__main__":
    main()

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