概要

生徒を得点の高い順（同点なら出席番号の小さい順）に並べたとき、\(K\) 番目の生徒の出席番号を求める問題です。

考察

この問題では、2つの基準でソートする「複合ソート」が必要です。

重要な気づき: 1. 各生徒について「得点」と「出席番号」の両方を保持する必要がある 2. ソートの優先順位は「得点（降順）」が第1、「出席番号（昇順）」が第2 3. ソート後に \(K\) 番目の要素を取り出せばよい

具体例で考える:

例えば \(N = 5\)、\(K = 3\)、得点が \(S = [80, 90, 80, 70, 90]\) の場合：

これをソートすると： 1. 出席番号 2（得点 90） 2. 出席番号 5（得点 90）← 同点だが出席番号が大きいので2番目 3. 出席番号 1（得点 80） 4. 出席番号 3（得点 80） 5. 出席番号 4（得点 70）

よって \(K = 3\) 番目は出席番号 1 となります。

素朴なアプローチで問題ない理由: \(N \leq 2 \times 10^5\) であり、ソートの計算量は \(O(N \log N)\) なので、十分高速に処理できます。

アルゴリズム

1. データ構造の準備: 各生徒について (得点, 出席番号) のタプルを作成してリストに格納
2. ソート: 得点の降順、同点の場合は出席番号の昇順でソート
   • Pythonでは key=lambda x: (-x[0], x[1]) とすることで実現
   • 得点を負の値 -x[0] にすることで、昇順ソートが降順ソートになる
3. 答えの出力: ソート後のリストの \(K-1\) 番目（0-indexed）の要素から出席番号を取り出す

計算量

• 時間計算量: \(O(N \log N)\)（ソートが支配的）
• 空間計算量: \(O(N)\)（生徒情報を格納するリストの分）

実装のポイント

1. 出席番号は1始まり: Pythonのリストは0-indexedなので、i + 1 として出席番号を作成する

2. 複合ソートのキー: (-得点, 出席番号) というタプルをキーにすることで、得点の降順・出席番号の昇順を一度のソートで実現できる

3. K番目の取り出し: ソート後のリストから K-1 番目（0-indexed）の要素を取り出すことを忘れずに

   ソースコード

N, K = map(int, input().split())
S = list(map(int, input().split()))

# (得点, 出席番号) のリストを作成
# 出席番号は1から始まる
students = [(S[i], i + 1) for i in range(N)]

# 得点の降順、同点の場合は出席番号の昇順でソート
students.sort(key=lambda x: (-x[0], x[1]))

# K番目（0-indexed で K-1）の生徒の出席番号を出力
print(students[K - 1][1])

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