概要

参加者を「獲得スコア」「レーティング」「参加者番号」の3つの基準で優先順位をつけてソートし、順位表を作成する問題です。

考察

この問題では、複数の条件に基づいてソートを行う必要があります。

問題の整理

順位を決める3つのルールを優先度の高い順に並べると： 1. 獲得スコア \(B_i\) が高い → 上位 2. レーティング \(A_i\) が高い → 上位（スコアが同じ場合） 3. 参加者番号 \(i\) が小さい → 上位（スコアもレーティングも同じ場合）

具体例で考える

例えば、以下の3人がいたとします： - 参加者1: レーティング=100, スコア=200 - 参加者2: レーティング=150, スコア=200 - 参加者3: レーティング=100, スコア=300

この場合： - 参加者3はスコア300で最も高いので 1位 - 参加者1と2はスコアが同じ200なので、レーティングで比較 - 参加者2はレーティング150 > 参加者1のレーティング100 なので 2位 - 参加者1が 3位

素朴なアプローチとの比較

この問題は単純なソートで解けるため、特にTLEやWAになりやすい罠はありません。ただし、ソートの条件を正しく設定することが重要です。

アルゴリズム

Pythonの sort() 関数を使って、複合キーによるソートを行います。

ソートキーの設計

Pythonの sort() はデフォルトで昇順（小さい順）にソートします。しかし今回は： - \(B\)（スコア）: 大きい順 → -B を使う - \(A\)（レーティング）: 大きい順 → -A を使う - \(i\)（参加者番号）: 小さい順 → そのまま i を使う

したがって、ソートキーを (-B, -A, i) とすることで、一度のソートで正しい順位を得られます。

処理の流れ

1. 入力を読み込み、各参加者の情報を (番号, レーティング, スコア) のタプルとしてリストに格納
2. ソートキー (-スコア, -レーティング, 番号) でソート
3. ソート後のリストから順番に参加者番号を出力

計算量

• 時間計算量: \(O(N \log N)\)
  • \(N\) 人の参加者をソートするため
• 空間計算量: \(O(N)\)
  • 参加者の情報を格納するリストに必要

実装のポイント

1. 参加者番号は1から始まる: for i in range(1, N + 1) として、1-indexedで番号を管理します。

2. ソートキーの符号に注意: 「大きい順」にしたい項目には -（マイナス）をつけます。これにより、昇順ソートでも降順の効果が得られます。

3. タプルの比較順序: Pythonのタプルは前から順に比較されるため、(-B, -A, i) という順序で指定すれば、問題文の優先順位どおりにソートされます。

4. 高速な入力: \(N\) が最大 \(2 \times 10^5\) と大きいため、sys.stdin.readline を使って入力を高速化しています。

   ソースコード

import sys

def main():
    input = sys.stdin.readline
    N = int(input())
    participants = []
    for i in range(1, N + 1):
        A, B = map(int, input().split())
        participants.append((i, A, B))
    
    # ソートキー: (-B, -A, i) で昇順ソート
    # Bが大きい順 → Aが大きい順 → 番号が小さい順
    participants.sort(key=lambda x: (-x[2], -x[1], x[0]))
    
    for p in participants:
        print(p[0])

if __name__ == "__main__":
    main()

---

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