概要

\(N\) 台のロボットがシングルエリミネーション方式のトーナメントで戦うとき、戦闘力が高いロボットが勝ち抜いていく。最初の配置順が与えられたとき、最終的に優勝するロボットの番号を求めよ。

考察

この問題は、トーナメント形式の戦いをシミュレーションするだけの問題です。ロボットは番号 \(1\) から \(N\) まで順に並んでおり、隣り合う2台ずつが戦って強い方が勝ち、次のラウンドに進むという流れを繰り返します。

例えば、\(N=4\) で戦闘力が \([10, 5, 8, 3]\) の場合を考えましょう。ロボット番号はそれぞれ \(1, 2, 3, 4\) です。

• 1回戦：

  • ロボット1 vs ロボット2 → 10 vs 5 → ロボット1が勝つ
  • ロボット3 vs ロボット4 → 8 vs 3 → ロボット3が勝つ

• 2回戦（勝者が順に並ぶ）：

  • ロボット1 vs ロボット3 → 10 vs 8 → ロボット1が勝つ

よって、優勝するのはロボット1です。

このように、実際にトーナメントをシミュレーションすれば答えが求められます。

ただし、素朴に考えると、毎回新しいリストを作ったり、インデックスの管理を間違えるとバグの原因になります。また、Pythonなどの言語では入力の読み込み方法によってはTLEになることもあります。そのため、効率的な入力処理と、ロボット番号を直接追跡するように実装することが重要です。

アルゴリズム

解法としては、トーナメントをそのままシミュレーションします。

1. 最初に、ロボットの番号を管理するリスト robots を用意します（初期値は \(1, 2, ..., N\)）。
2. 各ラウンドで、robots を先頭から2つずつ取り出し、それらの戦闘力を比較して勝者を選びます。
3. 勝者だけを集めたリストを次のラウンドとして更新します。
4. 最終的に1台だけ残ったロボットが優勝者です。

この方法で、トーナメントの構造を忠実に再現できます。

計算量

• 時間計算量: \(O(N)\)
  各ラウンドでロボットの数が半分になるため、合計で \(N + N/2 + N/4 + \cdots \approx 2N\) 回の比較が行われる。
• 空間計算量: \(O(N)\)
  ロボット番号を保持するリストに最大 \(N\) 個の要素が必要。

実装のポイント

• ロボットの番号は1-indexedなので、配列アクセスの際はインデックスを1引く必要があります（例：robots[i] - 1）。
• 入力が大きい場合は高速な入力処理（sys.stdin.readなど）を使用することを検討しましょう。
• 各ラウンドで勝ち残ったロボットを新たなリストに保存し、それを次のラウンドの候補とすることで、トーナメントの進行を簡単にシミュレートできます。

## ソースコード

```python
def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    N = int(data[0])
    A = list(map(int, data[1:N+1]))
    
    # ロボット番号は1-indexedで管理
    robots = list(range(1, N + 1))
    
    while len(robots) > 1:
        next_round = []
        for i in range(0, len(robots), 2):
            left_idx = robots[i] - 1
            right_idx = robots[i + 1] - 1
            if A[left_idx] > A[right_idx]:
                next_round.append(robots[i])
            else:
                next_round.append(robots[i + 1])
        robots = next_round
    
    print(robots[0])

if __name__ == "__main__":
    main()

この解説は qwen3-coder-480b によって生成されました。