概要

戦闘力が高い方が必ず勝つトーナメントなので、最終的な優勝者は「戦闘力が最大のロボット」です。よって \(A_i\) の最大値を持つロボット番号を求めればよいです。

考察

このトーナメントでは、どの試合でも戦闘力が高いロボットが必ず勝ちます（しかも全員戦闘力が異なる）。
すると、戦闘力が全体で最も高いロボット \(M\) は、

• どの相手と当たっても必ず勝つ
• トーナメントの組み方（並び順や当たり方）に関係なく、最終的に必ず優勝する

ことが分かります。
つまり「トーナメント表を実際にシミュレーションする必要はなく、最大値を探すだけでよい」です。

例えば \(A=[5,1,4,3]\) なら、1回戦は (5 vs 1)→5, (4 vs 3)→4、決勝は (5 vs 4)→5 で優勝は戦闘力最大の 5 です。
並び順が違っても、最大の 5 は誰にも負けないため必ず優勝します。

素朴にラウンドごとに勝者配列を作ってシミュレーションしても正解は出ますが、結局「最大値を探す」ことと本質的に同じで、実装もやや冗長になります。ここでは最短で最大値（とその位置）を求めます。

アルゴリズム

1. 入力 \(A_1, A_2, \ldots, A_N\) を読む
2. 現在の最大戦闘力 best_val と、そのロボット番号 best_idx（\(1\) 始まり）を保持する
3. 左から順に見ていき、より大きい戦闘力を見つけたら更新する
4. 最後に best_idx を出力する

これは「配列の最大値の位置（argmax）」を求める処理です。

計算量

• 時間計算量: \(O(N)\)（1回ずつ見るだけ）
• 空間計算量: \(O(1)\)（最大値と位置だけを保持する場合。※コードでは入力配列を持つため実質 \(O(N)\) だが、解法としては \(O(1)\) でも可能）

実装のポイント

• ロボット番号は \(1\) 始まりなので、配列の添字 \(i\) に対して番号は \(i+1\) とする点に注意します。

• \(N \le 2^{20}\) と大きめなので、Python では sys.stdin.buffer.read() を使うと高速に入力できます。

  ソースコード

import sys

def main():
    data = sys.stdin.buffer.read().split()
    if not data:
        return
    n = int(data[0])
    a = list(map(int, data[1:1+n]))
    best_idx = 1
    best_val = a[0]
    for i in range(1, n):
        if a[i] > best_val:
            best_val = a[i]
            best_idx = i + 1
    print(best_idx)

if __name__ == "__main__":
    main()

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