概要

\(N\) 人の選手から、総合評価（\(A_i + B_i\)）が高い順、同点の場合は背番号が小さい順に \(K\) 人を選抜し、選ばれた選手の背番号を小さい順に出力する問題です。

考察

この問題は、問題文の指示通りに選手を並び替え（ソートし）、上位 \(K\) 人を選ぶことで解決できます。

順位を決めるルールは以下の2つです。 1. 総合評価（\(A_i + B_i\)）が大きい順（降順） 2. 総合評価が等しい場合は、背番号 \(i\) が小さい順（昇順）

プログラミング言語の標準的なソート機能（Pythonの sort() など）は、複数の要素を持つデータ（タプルや配列）をソートする際、1番目の要素で比較し、同じであれば2番目の要素で比較する、というように昇順で並び替えます。

しかし、今回のルールでは「総合評価は降順」「背番号は昇順」と、並び替えの向きが異なります。これを素直に実装しようとすると、独自の比較関数を定義するなどの手間がかかります。

そこで、総合評価にマイナス（\(-1\)）を掛けた値を比較に使うというテクニックが有効です。 例えば、総合評価が \(100\) と \(80\) の場合、マイナスを掛けると \(-100\) と \(-80\) になります。これを昇順（小さい順）に並べると \(-100, -80\) となり、元の総合評価の降順（大きい順）と同じ結果を得ることができます。

したがって、各選手について (-総合評価, 背番号) というペア（タプル）を作り、これをそのまま昇順ソートするだけで、問題の条件通りの順位付けが完了します。

アルゴリズム

1. 選手のデータを格納する空のリストを用意します。
2. 各選手 \(i \ (1 \leq i \leq N)\) について、総合評価 \(S_i = A_i + B_i\) を計算します。
3. リストに (-S_i, i) というタプルを追加します。
4. リストを昇順にソートします。これにより、総合評価が高い順、同点なら背番号が小さい順に選手が並びます。
5. ソートされたリストの先頭から \(K\) 人分の背番号を取り出し、新しいリストに格納します。
6. 選ばれた \(K\) 人の背番号を小さい順に出力するため、抽出したリストを昇順にソートします。
7. ソートした背番号を \(1\) 行ずつ出力します。

計算量

• 時間計算量: \(O(N \log N)\)
  • 選手のリストを作成する処理に \(O(N)\)
  • \(N\) 人の選手をソートする処理に \(O(N \log N)\)
  • 選ばれた \(K\) 人の背番号をソートする処理に \(O(K \log K)\)
  • 全体として最も重い処理は \(N\) 人のソートなので、\(O(N \log N)\) となります。制約の \(N \leq 2 \times 10^5\) に対して十分高速に動作します。
• 空間計算量: \(O(N)\)
  • \(N\) 人分の選手データを保持するリストと、入力データを保持するためのメモリとして \(O(N)\) の空間を使用します。

実装のポイント

• 入力の高速化: \(N\) が最大 \(2 \times 10^5\) と大きいため、Pythonでは sys.stdin.read().split() を用いて入力を一括で読み込むと、実行速度を大幅に改善できます。

• ソートの工夫: 前述の通り、(-総合評価, 背番号) のタプルを作成することで、Pythonの組み込みの sort() メソッドをそのまま活用でき、コードがシンプルかつ高速になります。

• 出力の高速化: print('\n'.join(...)) を使うことで、何度も print 関数を呼び出すオーバーヘッドを減らし、出力を高速化しています。

  ソースコード

import sys

def main():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    N = int(input_data[0])
    K = int(input_data[1])
    
    players = []
    it = iter(input_data[2:])
    for i in range(1, N + 1):
        score = int(next(it)) + int(next(it))
        players.append((-score, i))
        
    players.sort()
    
    selected = [players[i][1] for i in range(K)]
    selected.sort()
    
    print('\n'.join(map(str, selected)))

if __name__ == '__main__':
    main()

この解説は gemini-3.1-pro-thinking によって生成されました。