概要

スコアを高い順に並べたときの \(K\) 番目のスコア \(B_K\) を基準（閾値）として、元の参加者のうち「スコアが \(B_K\) 以上」の人数を数える問題です。

考察

表彰対象は「上位 \(K\) 人」ではなく、「\(K\) 位のスコアと同じ人も全員含める」ため、順位そのものよりも \(K\) 番目のスコア値（閾値） が重要になります。

例えばスコアを降順に並べて - \([100, 90, 90, 80, 70]\), \(K=2\)

このとき \(B_2 = 90\) なので、表彰対象は「\(90\) 以上」＝ \(100, 90, 90\) の 3人 です。単に \(K=2\) 人を出力してしまうと誤り（WA）になります。

素朴に「全参加者を順位付けして、同点処理をしながら数える」ことも可能ですが、本質は次の2ステップに分解できます： 1. \(B_K\)（\(K\) 番目のスコア）を求める
2. 元の配列から \(B_K\) 以上の個数を数える

この形にすると実装が簡潔でミスが減ります。

アルゴリズム

1. スコア配列 \(A\) を降順にソートした配列 \(A\_sorted\) を作る。
2. 閾値 \(threshold = A\_sorted[K-1]\)（0-indexなので \(K-1\)）を取り出す。これは \(B_K\) に対応する。
3. 元の配列 \(A\) から、\(A_i \ge threshold\) を満たす要素数を数えて出力する。

ポイントは、ソートして得た \(K\) 番目のスコアを「閾値」として使い、同点者を自然に全員含めて数えられることです。

計算量

• 時間計算量: \(O(N \log N)\)（降順ソートが支配的、カウントは \(O(N)\)）
• 空間計算量: \(O(N)\)（ソート用配列など）

実装のポイント

• \(K\) 番目は 1-index なので、Python の 0-index 配列では K-1 に注意します。

• 閾値で数えるときは、ソート後ではなく 元の配列 を走査して >= threshold を数えればOKです（どちらでも結果は同じですが、元配列のまま数える方が意図が明確です）。

• 入力サイズが大きいので sys.stdin.buffer.read() でまとめて読み込むと高速です。

  ソースコード

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    N, K = data[0], data[1]
    A = data[2:]
    A_sorted = sorted(A, reverse=True)
    threshold = A_sorted[K - 1]
    ans = sum(1 for x in A if x >= threshold)
    print(ans)

if __name__ == "__main__":
    main()

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