概要

\(N\) 台のロボットがシングルエリミネーション形式（勝ち抜き戦）のトーナメントを行うとき、最終的な優勝者の番号を求める問題です。対戦では常に戦闘力が高い方のロボットが勝利します。

考察

この問題の最も重要なポイントは、「一度も負けずに最後まで勝ち残るのは誰か」を考えることです。

問題文にはトーナメントの組み方（1番と2番、3番と4番が戦う…など）が詳しく説明されていますが、対戦のルールに注目してみましょう。「戦闘力が高いロボットが必ず勝つ」というルールがあります。

もし、全ロボットの中で最も戦闘力が高いロボット（戦闘力が最大値のロボット）がどこかの試合に出場したとすると、相手が誰であっても必ず勝利します。このロボットはどのラウンドでも負けることがないため、最終的に必ず優勝することになります。

したがって、複雑なトーナメントのシミュレーションを行う必要はなく、「全ロボットの中で戦闘力 \(A_i\) が最大であるロボットの番号」を探すだけで正解を導き出すことができます。

具体例

例えば、ロボットの戦闘力が \([10, 50, 30, 20]\) だった場合： 1. 第1ラウンド： - ロボット1 (10) vs ロボット2 (50) → ロボット2の勝利 - ロボット3 (30) vs ロボット4 (20) → ロボット3の勝利 2. 第2ラウンド（決勝）： - ロボット2 (50) vs ロボット3 (30) → ロボット2の勝利

結果、最も戦闘力が高い「50」を持つロボット2が優勝します。

アルゴリズム

1. 入力された戦闘力のリスト \(A\) の中から、最大値 max_val を見つけます。
2. その最大値 max_val がリストの何番目にあるか（インデックス）を探します。
3. プログラミング言語の多くは添字が 0 から始まりますが、問題のロボット番号は 1 から始まるため、インデックスに 1 を加えた値を出力します。

計算量

• 時間計算量: \(O(N)\)
  • リストの中から最大値を探す処理、およびその位置を探す処理は、それぞれリストの要素数 \(N\) に対して比例する時間で終わります。\(N = 2^{20} \approx 10^6\) ですが、現代のコンピュータでは十分に高速に処理可能です。
• 空間計算量: \(O(N)\)
  • \(N\) 個の戦闘力を保持するためのメモリが必要です。

実装のポイント

• Pythonでは max(a) で最大値を、a.index(max_val) でその位置を取得できます。

• 入力サイズ \(N\) が最大で \(2^{20}\) と大きいため、sys.stdin.read().split() を用いて一括で入力を読み込むことで、実行時間を短縮しています。

• 最後に 1 を足して 1-indexed に直すのを忘れないようにしましょう。

  ソースコード

import sys

def solve():
    # 全ての入力を読み込み、空白や改行で分割してリストにする
    data = sys.stdin.read().split()
    if not data:
        return
    
    # ロボットの台数 N (data[0]) は使用せず、戦闘力のリストを作成する
    # data[1:] にはロボット1からNまでの戦闘力 A_i が格納されている
    try:
        a = list(map(int, data[1:]))
    except ValueError:
        return
    
    if not a:
        return
    
    # 戦闘力が高いロボットが必ず勝つトーナメント形式では、
    # 全ロボットの中で最大の戦闘力を持つロボットが最終的な優勝者となる
    max_val = max(a)
    
    # 優勝したロボットの番号（1-indexed）を求める
    # a.index(max_val) は 0-indexed なので 1 を加える
    winner_id = a.index(max_val) + 1
    
    # 結果を出力する
    sys.stdout.write(str(winner_id) + '\n')

if __name__ == '__main__':
    solve()

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