概要

\(N\) 人の参加者のスコアから上位 \(K\) 番目のスコア（ボーダーライン）を特定し、そのスコア以上を獲得した参加者の総数を求める問題です。

考察

問題文の通り、まずは参加者のスコアを大きい順に並べたときの \(K\) 番目のスコア \(B_K\) を見つける必要があります。この \(B_K\) が表彰されるための「ボーダーライン」となります。

ボーダーライン以上のスコアを持つ人を数えればよいのですが、制約の \(N \leq 2 \times 10^5\) に注目します。スコアの比較や人数のカウントに無駄な二重ループなどを使ってしまうと、計算量が \(O(N^2)\) となり実行時間制限（TLE）に引っかかってしまいます。

そこで、スコアの配列をソート（並び替え）するアプローチをとります。ソートの計算量は \(O(N \log N)\) なので、この制約でも十分に高速です。 配列をソートすれば、ボーダーラインのスコアは簡単に特定できます。さらに、ソート済みの配列であることを活かせば、二分探索を用いることで「ボーダー以上の人が何人いるか」を \(O(\log N)\) で高速に求めることができます。（※順番に数えても \(O(N)\) なので間に合いますが、二分探索を使うとよりスマートで汎用的な実装になります）

アルゴリズム

1. 参加者のスコア配列 \(A\) を昇順（小さい順）にソートします。
2. 昇順に並べた場合、上位 \(K\) 番目のスコアは「後ろから \(K\) 番目」の要素になります。これをボーダーライン（border）とします。
3. 二分探索アルゴリズムを用いて、配列 \(A\) の中で border 以上のスコアが最初に現れる位置（インデックス）を探します。
4. 全体の人数 \(N\) からそのインデックスを引いた値が、ボーダーライン以上のスコアを持つ参加者の人数となります。

具体例: スコアが A = [10, 20, 30, 40, 40, 50] で \(K=3\) の場合 - 後ろから3番目のスコアは 40 なので、ボーダーは 40 です。 - 40 以上が最初に現れるのはインデックス 3 （0始まり）です。 - 全体の人数 \(6\) から \(3\) を引いた 3 人が表彰対象となります。

計算量

• 時間計算量: \(O(N \log N)\)
  • 配列のソートに \(O(N \log N)\) かかります。
  • 二分探索（bisect_left）に \(O(\log N)\) かかります。
  • 全体として \(O(N \log N)\) となり、実行時間制限に余裕で間に合います。
• 空間計算量: \(O(N)\)
  • \(N\) 人分のスコアを配列として保持するために使用します。

実装のポイント

• 負のインデックスの活用 Pythonでは配列の後ろから要素にアクセスする際、負のインデックスを使うことができます。昇順ソートされた配列において、上位 \(K\) 番目の要素は A[-K] と書くことで直感的に取得できます。

• bisect_left の働き Pythonの標準ライブラリ bisect モジュールの bisect_left(A, x) は、ソート済みの配列 A に対して、値 x を挿入すべき最も左のインデックス（＝ x 以上の値が最初に現れる位置）を返します。これを利用することで、条件を満たす要素の個数を N - bisect_left(A, border) という1行で簡単に計算できます。

  ソースコード

import sys
import bisect

def main():
    input = sys.stdin.read
    data = input().split()
    if not data:
        return
    N = int(data[0])
    K = int(data[1])
    A = [int(x) for x in data[2:]]
    
    A.sort()
    border = A[-K]
    ans = N - bisect.bisect_left(A, border)
    print(ans)

if __name__ == '__main__':
    main()

この解説は gemini-3.1-pro-thinking によって生成されました。