概要

生徒の得点と出席番号に基づいて、得点の高い順（同点の場合は出席番号の小さい順）に並べたときの上位 \(K\) 番目の生徒の出席番号を求めます。

考察

この問題では、生徒の得点が高い順に並び替える必要があります。ただし、得点が同じ生徒が複数いる場合は、その中で出席番号が小さい順に並ぶ必要があります。

素朴な方法として、毎回最大得点の生徒を探すような方法（選択ソートなど）を取ると、最悪の場合 \(O(N^2)\) の計算時間が必要になり、制約 \(N \leq 2 \times 10^5\) に対しては時間内に解けません（TLE）。

そこで、すべての生徒を一度にソートしてしまうことを考えます。各生徒を「得点」と「出席番号」の組として扱い、ソートのキーを工夫することで、条件通りの順序で効率的に並べ替えることができます。

アルゴリズム

1. 各生徒について、「得点」と「出席番号」のペアを持ったリストを作成します。
2. このリストを以下のようにソートします：
   • 得点が高い順（降順）
   • 得点が同じなら出席番号が小さい順（昇順）
3. ソート後に、先頭から \(K\) 番目の要素に対応する出席番号を出力します。

たとえば、入力例：

N = 5, K = 3
S = [80, 90, 90, 70, 80]

このとき、生徒情報は： - 生徒1: 80点 - 生徒2: 90点 - 生徒3: 90点 - 生徒4: 70点 - 生徒5: 80点

ペアにすると：

[(80, 1), (90, 2), (90, 3), (70, 4), (80, 5)]

これをソートすると：

[(90, 2), (90, 3), (80, 1), (80, 5), (70, 4)]

上から3番目は (80, 1) なので、答えは出席番号 1 になります。

計算量

• 時間計算量: \(O(N \log N)\)（ソートによる）
• 空間計算量: \(O(N)\)（生徒情報を保持するリスト）

実装のポイント

• ソートキーを (-得点, 出席番号) のように設定することで、得点の降順・出席番号の昇順を一度に実現できます。
• 出席番号は1-indexedなので、インデックスをずらさないように注意してください（コードでは i+1 としています）。

## ソースコード

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

# (得点, 出席番号) のリストを作成し、得点の降順、出席番号の昇順でソート
students = [(S[i], i + 1) for i in range(N)]
students.sort(key=lambda x: (-x[0], x[1]))

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

---

この解説は qwen3-coder-480b によって生成されました。