概要

スコアを降順にソートしたとき、\(K\) 番目のスコア以上の参加者が何人いるかを数える問題です。同点の参加者も全員表彰する点がポイントです。

考察

まず問題を整理しましょう。「上位 \(K\) 人を表彰するが、\(K\) 位と同じスコアの人も全員表彰する」というルールです。

具体例で考えてみましょう。

例えば \(N = 6\), \(K = 3\), スコアが [100, 90, 80, 80, 70, 60] の場合：

• 降順に並べると \(B = [100, 90, 80, 80, 70, 60]\)
• \(K = 3\) 番目のスコアは \(B_3 = 80\)
• スコアが \(80\) 以上の人は \(100, 90, 80, 80\) の 4人
• よって表彰対象は 4 人（\(K = 3\) 人より多い）

このように、\(K\) 位のスコア（ボーダーライン）を求め、そのスコア以上の人を全員数えればよいことがわかります。

素朴なアプローチで問題はないか？

この問題では、ソートして \(K\) 番目の値を取り出し、それ以上の人数を数えるだけなので、特に TLE になるような罠はありません。ソートが最も重い処理で \(O(N \log N)\) ですが、\(N \leq 2 \times 10^5\) なので十分高速です。

アルゴリズム

1. スコアの配列 \(A\) を降順（大きい順）にソートする。
2. ソート後の配列の \(K\) 番目（0-indexed では \(K-1\) 番目）の値をボーダーライン \(threshold\) とする。
3. 配列 \(A\) の中で \(threshold\) 以上の要素の個数を数える。
4. その個数が答え。

ステップごとの例（\(N=5, K=2, A=[50, 80, 80, 30, 90]\)）：

1. 降順ソート → \([90, 80, 80, 50, 30]\)
2. \(K=2\) 番目（0-indexed で \(1\) 番目）→ \(threshold = 80\)
3. \(80\) 以上の要素: \(90, 80, 80\) → 3個
4. 答え: 3

計算量

• 時間計算量: \(O(N \log N)\)（ソートが支配的）
• 空間計算量: \(O(N)\)（スコアの配列を保持）

実装のポイント

• Python のリストのインデックスは 0-indexed なので、\(K\) 番目のスコアは A[K - 1] であることに注意しましょう。

• A.sort(reverse=True) で降順ソートを行います。sorted() を使っても構いません。

• 表彰人数のカウントは、sum(1 for a in A if a >= threshold) のようにジェネレータ式を使うとシンプルに書けます。もちろん for ループでカウント変数を使っても問題ありません。

  ソースコード

N, K = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse=True)
threshold = A[K - 1]
print(sum(1 for a in A if a >= threshold))

---

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