概要

与えられたN人のスコアから、K位以上の参加者と同点の参加者全員を表彰対象とする際の人数を求める問題です。

考察

問題の条件を正確に理解することが重要です。スコアを降順に並べたとき、K番目のスコア（B_K）以上のスコアを持つ参加者全員が表彰対象となります。つまり、K位の参加者と同じスコアの参加者が複数人いる場合、それら全員が表彰されるため、K人より多くなる可能性があります。

素朴なアプローチとして、スコアを全てソートした後、K番目のスコア（閾値）を求め、その閾値以上のスコアを持つ人数を数えることで正解が得られます。制約条件がN ≤ 2×10^5なので、効率的なソートアルゴリズム（O(N log N)）を使用すれば十分高速です。

アルゴリズム

1. 参加者のスコアを降順（大きい順）にソートする
2. K番目のスコア（インデックスではK-1番目）を閾値として取得する
3. ソート済みのスコアリストを先頭から走査し、閾値以上のスコアを持つ人数を数える
   • 降順ソートされているため、一度閾値未満のスコアが出たらそれ以降は調べる必要がない

計算量

• 時間計算量: \(O(N \log N)\)
  • スコアのソートに最も時間がかかる
  • その後の走査は最悪ケースでも\(O(N)\)
• 空間計算量: \(O(N)\)
  • スコアを格納するための配列が必要

実装のポイント

• ソートは降順（reverse=True）で行う必要がある

• K番目のスコアはインデックスK-1でアクセスできる（0-indexedのため）

• 走査時に閾値未満のスコアが出た時点でループを打ち切れる（効率化）

• 入力値の読み取りはsys.stdin.read()を使用して一度に読み込むことで高速化できる

  ソースコード

def main():
    import sys
    data = sys.stdin.read().split()
    n = int(data[0])
    k = int(data[1])
    scores = list(map(int, data[2:2+n]))
    scores.sort(reverse=True)
    threshold = scores[k-1]
    count = 0
    for score in scores:
        if score >= threshold:
            count += 1
        else:
            break
    print(count)

if __name__ == "__main__":
    main()

この解説は deepseekv3 によって生成されました。