概要

各選手の総合評価 \(A_i+B_i\) が高い順（同点なら背番号が小さい順）に並べ、上位 \(K\) 人の背番号を小さい順に出力する問題です。

考察

順位付けのルールは「キーが2つあるソート」としてそのまま扱えます。

• まず総合評価 \(S_i = A_i + B_i\) を計算する。
• 順位は
  
  1. \(S_i\) が大きいほど上位
     
  2. \(S_i\) が同じなら背番号 \(i\) が小さいほど上位
     なので、「\((S_i\) の降順, \(i\) の昇順)」で並べれば順位が一意に決まります。

素朴に「上位を1人ずつ探す（毎回最大を走査）」をすると、\(K\) 回の探索で \(O(NK)\) となり、最大で \((2\times10^5)^2\) 近くになって間に合いません。
そこで、最初に全員を一度だけソートして順位を確定させればよく、これなら \(O(N\log N)\) で十分高速です。

最後に求める出力は「選ばれた \(K\) 人の背番号を小さい順」なので、上位 \(K\) 人を取り出した後に背番号だけをもう一度昇順ソートします。

アルゴリズム

1. 入力を受け取り、各選手 \(i\) について総合評価 \(S_i=A_i+B_i\) を計算する。
2. 各選手をタプル (-S_i, i) として配列に入れる。
   
   • Python の sort() は昇順なので、-S_i にして「総合評価の降順」を実現する。
     
   • 同点時はタプルの第2要素 i（背番号）が小さい方が先になり、条件を満たす。
3. 配列をソートし、先頭から \(K\) 個の背番号を取り出す（これが順位 \(1\) 位〜\(K\) 位）。
4. 取り出した背番号を昇順にソートして、1行ずつ出力する。

（例）総合評価が [10(背番号2), 10(背番号5), 9(背番号1)] なら、同点では背番号が小さい 2 が 5 より上位になる、という動きがタプルソートで自然に実現されます。

計算量

• 時間計算量: \(O(N\log N)\)（全体ソート）＋ \(O(K\log K)\)（選抜後の背番号ソート）
• 空間計算量: \(O(N)\)（選手情報の配列）

実装のポイント

• ソートキーを (- (A_i+B_i), i) にすることで、「総合評価は降順、背番号は昇順」を1回のソートで表現できます。

• 入力サイズが大きいので sys.stdin.buffer.read() でまとめ読みすると高速です。

• 出力は「背番号の昇順」なので、上位 \(K\) 人を取った後にもう一度 selected_ids.sort() が必要です。

  ソースコード

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    N, K = data[0], data[1]
    players = []
    idx = 2
    for i in range(1, N + 1):
        a = data[idx]
        b = data[idx + 1]
        idx += 2
        players.append((-(a + b), i))  # sort by score desc, id asc

    players.sort()
    selected_ids = [pid for _, pid in players[:K]]
    selected_ids.sort()

    sys.stdout.write("\n".join(map(str, selected_ids)))

if __name__ == "__main__":
    main()

この解説は gpt-5.2-high によって生成されました。