概要

選手の総合評価と背番号に基づいて順位を決め、上位 \(K\) 人を選抜し、その背番号を昇順に出力する問題。

考察

この問題では、各選手の「総合評価」を \(A_i + B_i\) として求め、それに基づいて順位を付ける必要があります。ただし、総合評価が同じ選手が複数いる場合、背番号が小さい方が上位となります。これはソートにおける優先順位の決め方に関係しており、「第一キー：総合評価（降順）」、「第二キー：背番号（昇順）」という条件でソートを行う必要があります。

素朴な方法としては、すべての選手について総合評価を計算し、それを元に順位を決めて上位 \(K\) 人を選ぶという流れになります。しかし、単にリスト操作などで毎回ソートを行うと、最悪ケースで \(O(N^2)\) などになってしまう可能性があり、制約 \(N \leq 2 \times 10^5\) に対しては時間内に終わらない可能性があります。

そこで、Pythonの組み込みソート（Timsort）を利用することで、効率的にソートを行うことができます。このソートは安定かつ高速であり、適切なキーを指定することで目的の順序で並び替えることが可能です。

さらに、選ばれた上位 \(K\) 人の背番号を昇順に出力する必要があるため、一度選抜された選手たちを再度背番号順にソートする必要があります。

アルゴリズム

1. 各選手の総合評価 \(A_i + B_i\) を計算し、背番号とともにタプル \((\text{総合評価}, \text{背番号})\) としてリストに保存する。
2. リストを以下のようにソートする：
   • 第一キー：総合評価（降順）
   • 第二キー：背番号（昇順）
3. ソート後のリストの先頭 \(K\) 件を取り出す。
4. 取り出した \(K\) 人の背番号を昇順にソートしなおす。
5. 背番号を順番に出力する。

例

入力が以下のとき：

5 3
80 90
70 80
90 80
80 80
90 90

各選手の総合評価は： - 選手1: \(80 + 90 = 170\) - 選手2: \(70 + 80 = 150\) - 選手3: \(90 + 80 = 170\) - 選手4: \(80 + 80 = 160\) - 選手5: \(90 + 90 = 180\)

\((\text{総合評価}, \text{背番号})\) のリストは： $\( [(170, 1), (150, 2), (170, 3), (160, 4), (180, 5)] \)$

これをソートすると： $\( [(180, 5), (170, 1), (170, 3), (160, 4), (150, 2)] \)$

上位3人は背番号5, 1, 3。これらを背番号順に並べると： $\( [1, 3, 5] \)$

出力：

1
3
5

計算量

• 時間計算量: \(O(N \log N)\)
  （リストのソートが支配的）
• 空間計算量: \(O(N)\)
  （選手情報を格納するリスト）

実装のポイント

• タプルを使って、複数のキーでソートできるようにする。

• ソートキーを (-総合評価, 背番号) とすることで、降順・昇順を同時に表現できる。

• 上位 \(K\) 人を選んだ後、最終的な出力のために背番号順に再ソートすることを忘れない。

  ソースコード

import sys
input = sys.stdin.read

def main():
    data = input().split()
    N = int(data[0])
    K = int(data[1])
    
    players = []
    index = 2
    for i in range(N):
        A = int(data[index])
        B = int(data[index+1])
        total = A + B
        players.append((total, i+1))  # (総合評価, 背番号)
        index += 2
    
    # 総合評価の降順、背番号の昇順でソート
    players.sort(key=lambda x: (-x[0], x[1]))
    
    # 上位K人を取得し、背番号で再ソート
    selected = players[:K]
    selected.sort(key=lambda x: x[1])
    
    for _, num in selected:
        print(num)

if __name__ == "__main__":
    main()

---

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