概要

各参加者のスコアとレーティングに基づいて、指定されたルールに従って順位を決定し、上位から参加者番号を出力する問題です。

考察

この問題では、各参加者に以下の3つの情報があります：

• 獲得スコア \(B_i\)
• レーティング \(A_i\)
• 参加者番号 \(i\)

順位の決め方は以下の通りです：

1. スコアが高い順（降順）
2. スコアが同じならレーティングが高い順（降順）
3. それも同じなら参加者番号が小さい順（昇順）

したがって、これらの情報を一つのタプルにしてソートすることで順位を決定できます。

素朴な方法として、毎回最大値を探すような処理を行うと、最悪ケースで \(O(N^2)\) となり、制約 \(N \leq 2 \times 10^5\) ではTLEしてしまいます。そこで、一度に全体をソートする方法を考えます。

Python では sort() 関数に比較キーを指定できるので、この3つの条件を適切に設定してソートするのが効率的です。

具体的には、(B_i, A_i, i) のタプルを以下のようにソートします：

• 第一キー：\(B_i\) （降順 → -B_i）
• 第二キー：\(A_i\) （降順 → -A_i）
• 第三キー：\(i\) （昇順）

このようにキーを設定することで、問題の順位ルールに沿ったソートが可能です。

アルゴリズム

1. 各参加者について (B_i, A_i, i) のタプルを作成し、リストに格納する。
2. このリストを以下のキーでソートする：
   • -B_i（スコアの降順）
   • -A_i（レーティングの降順）
   • i（番号の昇順）
3. ソートされた順に参加者番号を出力する。

計算量

• 時間計算量: \(O(N \log N)\)（ソートによる）
• 空間計算量: \(O(N)\)（参加者情報の保存）

実装のポイント

• 入力を高速に読み込むために sys.stdin.read を使用している。
• ソートキーを (-B, -A, i) のように設定することで、複数条件を一度に扱える。
• タプルの要素を取り出す際、アンダースコア _ を使って無視する変数を明示的に表現すると可読性が上がる。

## ソースコード

```python
import sys
input = sys.stdin.read

data = input().split()
N = int(data[0])
participants = []

index = 1
for i in range(N):
    A = int(data[index])
    B = int(data[index+1])
    participants.append((B, A, i+1))
    index += 2

participants.sort(key=lambda x: (-x[0], -x[1], x[2]))

for _, _, num in participants:
    print(num)

---

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