概要

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

考察

問題の順位決定ルールは以下の3つです： 1. スコア \(B_i\) が高い方が上位 2. スコアが同じ場合はレーティング \(A_i\) が高い方が上位 3. スコアとレーティングが同じ場合は参加者番号が小さい方が上位

各参加者のデータを単純に比較してソートするだけで、正しい順序を得ることができます。ただし、ソートの際に複数のキーを同時に考慮する必要があります。

アルゴリズム

1. 各参加者のデータを \((B_i, A_i, i+1)\) のタプルとしてリストに格納します
2. ソートキーを以下のように指定して降順/昇順ソートします：
   • 第一キー：スコア \(B_i\)（降順：-x[0]）
   • 第二キー：レーティング \(A_i\)（降順：-x[1]）
   • 第三キー：参加者番号（昇順：x[2]）
3. ソート後のリストの参加者番号を順に出力します

計算量

• 時間計算量: \(O(N \log N)\)
  • ソートアルゴリズムの計算量が支配的です
• 空間計算量: \(O(N)\)
  • 参加者データを格納するためのリストが必要です

実装のポイント

• Pythonのsorted関数やlist.sort()メソッドは、複数キーでのソートを簡単に実装できます

• 降順ソートが必要なキーには負の値（-x[0]）を使用することで、昇順ソートを利用して降順を表現できます

• 入力データの読み込みでは、一度にすべてのデータを読み込む方法が効率的です

  ソースコード

import sys

def main():
    data = sys.stdin.read().split()
    n = int(data[0])
    participants = []
    index = 1
    for i in range(n):
        a = int(data[index])
        b = int(data[index+1])
        index += 2
        participants.append((b, a, i+1))
    
    participants.sort(key=lambda x: (-x[0], -x[1], x[2]))
    
    for p in participants:
        print(p[2])

if __name__ == "__main__":
    main()

この解説は deepseekv3 によって生成されました。