概要

シングルエリミネーション形式のトーナメント戦をシミュレーションし、優勝するロボットの番号を求める問題です。

考察

問題の理解

トーナメント戦では、隣り合う2台のロボットが対戦し、戦闘力が高い方が勝ち残ります。これを繰り返して最後の1台になるまで続けます。

例えば \(N = 4\) で戦闘力が \(A = [3, 7, 2, 5]\) の場合： - ラウンド1: - ロボット1（戦闘力3） vs ロボット2（戦闘力7） → ロボット2の勝ち - ロボット3（戦闘力2） vs ロボット4（戦闘力5） → ロボット4の勝ち - ラウンド2（決勝）: - ロボット2（戦闘力7） vs ロボット4（戦闘力5） → ロボット2の勝ち

よって優勝はロボット2です。

素朴なアプローチで問題ない理由

この問題では、各ラウンドでロボットの数が半分になります。\(N\) 台から始めると、ラウンド数は \(\log_2 N\) 回です。

• ラウンド1: \(N/2\) 試合
• ラウンド2: \(N/4\) 試合
• …
• 最終ラウンド: 1試合

総試合数は \(N/2 + N/4 + \cdots + 1 = N - 1\) 回となり、\(N \leq 2^{20} \approx 10^6\) でも十分高速に処理できます。

アルゴリズム

1. 各ロボットを「(戦闘力, ロボット番号)」のペアとしてリストに格納する
2. 以下をロボットが1台になるまで繰り返す：
   • 隣り合う2台ずつを比較し、戦闘力が高い方を次のラウンドに進める
   • 次のラウンドに進むロボットたちで新しいリストを作る
3. 最後に残ったロボットの番号を出力する

初期状態: [(3,1), (7,2), (2,3), (5,4)]
    ↓ ラウンド1
[(7,2), (5,4)]
    ↓ ラウンド2
[(7,2)]
    ↓
優勝: ロボット2

計算量

• 時間計算量: \(O(N)\)
  • 各ラウンドの試合数の合計は \(N/2 + N/4 + \cdots + 1 = N - 1\) 回
• 空間計算量: \(O(N)\)
  • ロボットの情報を格納するリストに \(O(N)\) の空間が必要

実装のポイント

1. ロボット番号の管理: 戦闘力だけでなく、元のロボット番号も一緒に保持する必要があります。タプル (戦闘力, 番号) で管理すると便利です。

2. 1-indexed と 0-indexed の変換: 問題ではロボット番号が1から始まりますが、配列のインデックスは0から始まります。番号を i + 1 として保存することで対応しています。

3. 2台ずつの処理: for i in range(0, len(robots), 2) とすることで、インデックス 0, 2, 4, … と2つ飛ばしでループし、robots[i] と robots[i+1] のペアを処理できます。

   ソースコード

def solve():
    N = int(input())
    A = list(map(int, input().split()))
    
    # 各ロボットを(戦闘力, ロボット番号)のペアで管理
    # ロボット番号は1-indexed
    robots = [(A[i], i + 1) for i in range(N)]
    
    # トーナメントをシミュレーション
    while len(robots) > 1:
        next_round = []
        for i in range(0, len(robots), 2):
            # 隣り合う2台が対戦、戦闘力が高い方が勝つ
            if robots[i][0] > robots[i + 1][0]:
                next_round.append(robots[i])
            else:
                next_round.append(robots[i + 1])
        robots = next_round
    
    # 優勝ロボットの番号を出力
    print(robots[0][1])

solve()

---

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