概要

\(N\) 人の生徒を「得点の高い順」、得点が同じなら「出席番号の小さい順」に並べたとき、上から \(K\) 番目にくる生徒の出席番号を求める問題です。

考察

この問題を解くためには、複数の条件（得点と出席番号）を考慮してデータを並べ替える（ソートする）必要があります。

1. 並び替えの優先順位:

   • 第1優先：得点（大きいほど上）
   • 第2優先：出席番号（小さいほど上）

2. ソートの工夫: 多くのプログラミング言語の標準的なソート機能は「昇順（小さい順）」です。今回の第1優先である「得点の大きい順（降順）」をそのまま扱うと、少し工夫が必要です。 ここで便利なテクニックが、「得点に \(-1\) を掛けて負の値にする」という方法です。 例えば、得点が 100, 90, 100 の場合、\(-1\) を掛けると -100, -90, -100 となります。これを昇順で並べると -100, -100, -90 となり、元の得点の「大きい順」に対応させることができます。

3. データの保持: 「得点」と「出席番号」をセットで管理するために、タプル（Pythonの (a, b) 形式）を利用します。タプルをソートすると、1番目の要素で比較され、もし同じなら2番目の要素で比較されるという性質があるため、この問題の条件を自然に満たすことができます。

アルゴリズム

以下の手順で解くことができます。

1. 生徒 \(i\) の得点 \(S_i\) と出席番号 \(i\) をペアにし、(-S_i, i) という形のタプルを作成します。
2. 作成したタプルのリストをすべて読み込みます。
3. リストを昇順にソートします。
   • 第1要素の -S_i が小さい順（＝元の得点が高い順）に並びます。
   • 第1要素が同じなら、第2要素の i が小さい順（＝出席番号が小さい順）に並びます。
4. ソートされたリストの \(K\) 番目（プログラミングのインデックスでは \(K-1\)）の要素を取り出し、その出席番号を出力します。

計算量

• 時間計算量: \(O(N \log N)\)
  • データの読み込みに \(O(N)\)、ソートに \(O(N \log N)\) の時間がかかります。\(N = 2 \times 10^5\) の場合、\(N \log N\) は約 \(3.6 \times 10^6\) 程度であり、制限時間内に十分間に合います。
• 空間計算量: \(O(N)\)
  • \(N\) 人分のデータをリストに保持するため、人数に比例したメモリを使用します。

実装のポイント

• 高速な入出力: \(N\) が大きいため、Pythonでは input() よりも sys.stdin.read().split() を使うことで、入力速度を向上させています。

• 0-indexed: リストの \(K\) 番目の要素にアクセスする際は、インデックスが 0 から始まるため students[k - 1] と指定します。

• 出席番号: 問題文の出席番号は \(1\) から始まります。ループの変数 \(i\) を使って i + 1 とすることで正しく管理できます。

  ソースコード

import sys

def solve():
    # 標準入力から全てのデータを読み込み、空白で分割してリストに格納します
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N（生徒数）とK（求めたい順位）を取得します
    n = int(input_data[0])
    k = int(input_data[1])
    
    # 各生徒の情報を (-得点, 出席番号) のタプルとしてリストに格納します
    # 得点を負の値にすることで、昇順ソートした際に出席番号の昇順を保ちつつ、
    # 得点の高い順（得点の絶対値が大きい順）に並べることができます
    students = [(-int(input_data[i + 2]), i + 1) for i in range(n)]
    
    # タプルをソートします。第一要素（-得点）の昇順、
    # 第一要素が同じなら第二要素（出席番号）の昇順で並びます
    students.sort()
    
    # 上からK番目（インデックス K-1）の生徒の出席番号を出力します
    sys.stdout.write(str(students[k - 1][1]) + '\n')

if __name__ == '__main__':
    solve()

この解説は gemini-3-flash-preview によって生成されました。