概要

各選手の総合評価（練習評価点と試合評価点の和）で順位を付け、上位K人の背番号を小さい順に出力する問題です。

考察

問題のルールに従って順位を付けるには、まず各選手の総合評価（\(A_i + B_i\)）を計算する必要があります。総合評価が同じ場合は背番号が小さい方が上位になります。素朴なアプローチとして、すべての選手の総合評価を計算し、ルールに従ってソートすることで、上位K人を簡単に求めることができます。制約条件が\(N \leq 2 \times 10^5\)であるため、効率的なソートアルゴリズム（\(O(N \log N)\)）を使用すれば十分高速に処理できます。

アルゴリズム

1. 各選手について、総合評価（\(A_i + B_i\)）を計算します。
2. 選手を順位付けのルールに従ってソートします。具体的には、総合評価の降順（大きい順）でソートし、総合評価が同じ場合は背番号の昇順（小さい順）でソートします。
3. ソート後の上位K人の背番号を取得します。
4. 取得した背番号を小さい順（昇順）にソートして出力します。

計算量

• 時間計算量: \(O(N \log N)\)
  • 総合評価の計算に\(O(N)\)、選手のソートに\(O(N \log N)\)、背番号のソートに\(O(K \log K)\)（ただし\(K \leq N\)）かかりますが、全体としては\(O(N \log N)\)が支配的です。
• 空間計算量: \(O(N)\)
  • 選手の情報を格納する配列に\(O(N)\)のメモリを使用します。

実装のポイント

• ソートの際、総合評価の降順と背番号の昇順を同時に指定する必要があります。Pythonでは、タプルの要素を(-total, number)のようにして、総合評価は降順、背番号は昇順になるようにします。

• 最終的に背番号を小さい順に出力するため、上位K人の背番号を再度ソートします。

  ソースコード

def main():
    import sys
    data = sys.stdin.read().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])
        index += 2
        total = a + b
        players.append((total, i+1))
    
    players.sort(key=lambda x: (-x[0], x[1]))
    
    result = []
    for i in range(k):
        result.append(players[i][1])
    
    result.sort()
    for num in result:
        print(num)

if __name__ == "__main__":
    main()

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