概要

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

考察

この問題で重要なポイントは以下の通りです。

ソートの基準を正しく設定する

順位の付け方は2段階あります： 1. 総合評価が大きいほど上位（降順） 2. 総合評価が同じなら背番号が小さいほど上位（昇順）

例えば、3人の選手がいて \((A_i + B_i, \text{背番号})\) が以下のようだったとします：

背番号	総合評価
1	10
2	15
3	10

この場合、順位は「2番（評価15）→ 1番（評価10、背番号小）→ 3番（評価10、背番号大）」となります。

ソートキーの工夫

Pythonの sort() はデフォルトで昇順にソートします。総合評価は降順にしたいので、総合評価を負の値にしてソートキーに使うのがテクニックです。

各選手を \((-(A_i + B_i),\ i)\) というタプルで表すと： - 第1要素：総合評価の負値 → 昇順ソートすると、総合評価が大きい選手が先に来る - 第2要素：背番号 → 第1要素が同じ場合、背番号が小さい選手が先に来る

これにより、Pythonのデフォルトのタプル比較で正しい順位順にソートできます。

素朴なアプローチでも十分

\(N \leq 2 \times 10^5\) なので、\(O(N \log N)\) のソートで十分間に合います。特別なデータ構造は不要です。

アルゴリズム

1. \(N\) 人の選手それぞれについて、タプル \((-(A_i + B_i),\ i)\) を作成する。
2. このタプルのリストを昇順ソートする。
3. ソート後の先頭 \(K\) 個が上位 \(K\) 人に対応するので、その背番号を取り出す。
4. 取り出した \(K\) 個の背番号を小さい順にソートして出力する。

計算量

• 時間計算量: \(O(N \log N)\)
  • 全選手のソートに \(O(N \log N)\)、上位 \(K\) 人の背番号のソートに \(O(K \log K)\)。全体として \(O(N \log N)\)。
• 空間計算量: \(O(N)\)
  • 全選手のタプルを格納するリストに \(O(N)\)。

実装のポイント

• 負値によるソートの反転: Pythonでは sort(reverse=True) を使う方法もありますが、タプルの第1要素だけ降順・第2要素は昇順としたい場合、第1要素を負にするテクニックが簡潔で便利です。

• 高速な入力: \(N\) が最大 \(2 \times 10^5\) と大きいため、sys.stdin.buffer.read() で一括読み込みすることで入力処理を高速化しています。

• 出力の順序に注意: 上位 \(K\) 人を選んだ後、最終的な出力は「背番号の小さい順」である点を忘れないようにしましょう。選抜時のソート順（総合評価順）とは異なります。

  ソースコード

import sys

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    K = int(input_data[idx]); idx += 1
    
    players = []
    for i in range(1, N + 1):
        A = int(input_data[idx]); idx += 1
        B = int(input_data[idx]); idx += 1
        players.append((-(A + B), i))
    
    players.sort()
    
    selected = sorted(players[j][1] for j in range(K))
    
    print('\n'.join(map(str, selected)))

main()

---

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