概要

得点を「高い順、同点なら出席番号の小さい順」に並べたとき、上から \(K\) 番目の生徒の出席番号を求めます。

考察

この問題は「並べ替えの規則」が明確なので、素朴には生徒 \((i, S_i)\) を並べ替えて \(K\) 番目を取れば解けます。しかし \(N \le 2\times 10^5\) なので、通常のソートでも \(O(N\log N)\) で間に合うことが多い一方、もっと軽く解ける重要な観察があります。

• 得点 \(S_i\) の取り得る範囲が \(0 \le S_i \le 100\) と非常に小さい（101通りしかない）
• 同点のときは出席番号の小さい順 → つまり同じ得点グループの中では、出席番号を小さい順に並べればよい

この性質を使うと、得点ごとに生徒を「バケツ（bucket）」に入れておき、得点の高い方から順に人数を数えていけば、ソートをせずに \(K\) 番目を直接見つけられます。

例えば得点が - 90点: [2, 5] - 80点: [1, 4, 6] のようにバケツを作ると、順位表は 90点の [2,5] → 80点の [1,4,6] の順になります（同点内は出席番号が小さい順）。

アルゴリズム

1. 得点 \(0\) 〜 \(100\) の各点数に対応する配列 buckets[score] を用意する。
2. 生徒を出席番号順（\(1\) から \(N\)）に見ていき、得点が score の生徒の出席番号 i を buckets[score] に追加する。
   • 出席番号順に追加しているので、同じ得点のバケツ内は自動的に「出席番号の小さい順」になります。
3. 得点を \(100\) から \(0\) へ降順に見ていき、各バケツの人数を累積していく。
   • これまでに見た人数を cnt とすると、ある得点 score のバケツ b に対して
     cnt + len(b) >= K となった瞬間、\(K\) 番目はこのバケツ内に存在する。
4. バケツ内での位置は K - cnt - 1（0-indexed）なので、それを出力する。

計算量

• 時間計算量: \(O(N + 101) \simeq O(N)\)
• 空間計算量: \(O(N + 101) \simeq O(N)\)（バケツに出席番号を全員分保持するため）

実装のポイント

• 同点時の「出席番号の小さい順」を満たすために、入力を出席番号順（enumerate(..., start=1)）で走査し、その順でバケツに append します。これによりバケツ内の並び替えが不要になります。

• \(K\) 番目の要素を取り出すときは、0-indexed に注意して b[K - cnt - 1] とします。

• 入力が最大 \(2\times 10^5\) なので、Pythonでは sys.stdin.buffer.read() を使うと高速に読み取れます。

  ソースコード

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    N, K = data[0], data[1]
    S = data[2:]

    buckets = [[] for _ in range(101)]
    for i, score in enumerate(S, start=1):
        buckets[score].append(i)

    cnt = 0
    for score in range(100, -1, -1):
        b = buckets[score]
        if cnt + len(b) >= K:
            print(b[K - cnt - 1])
            return
        cnt += len(b)

if __name__ == "__main__":
    main()

この解説は gpt-5.2-high によって生成されました。