概要

選手 \(K\) が最大何回勝利できるかを、レーティングに基づいて求める問題です。

考察

この問題では、選手同士の勝敗がレーティングの大小関係によって完全に決定されます。つまり、レーティングが高い選手は必ず勝ち、低い選手は必ず負けます。したがって、選手 \(K\) がどれだけ多くの試合に勝てるかは、「選手 \(K\) よりもレーティングが低い選手の人数」に等しくなります。

例えば、選手 \(K\) のレーティングが \(100\) だったとします。他の選手中でレーティングが \(100\) よりも低い選手が \(3\) 人居れば、選手 \(K\) は最大で \(3\) 回勝つことができます。なぜなら、毎回そのような低いレーティングの選手と当たるようにトーナメントを組めばよいからです。

このように、トーナメントの組み方は自由なので、選手 \(K\) にとって不利な選手（レーティングが高く、最終的に選手 \(K\) を倒す可能性のある選手）を最後に遭遇させることで、勝利数を最大化できます。

したがって、必要なのは単純に「選手 \(K\) よりもレーティングが低い選手の数」を数えるだけです。

アルゴリズム

1. 選手 \(K\) のレーティング \(S_K\) を取得する。
2. 全選手中について、\(S_i < S_K\) となる選手の数をカウントする。
3. その数が選手 \(K\) が勝てる最大試合数となるので、それを出力する。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(1)\)

実装のポイント

• 選手の番号 \(K\) は1-indexedで与えられるので、配列のインデックスとしては \(K-1\) を使う必要がある。
• 単純に全探索でカウントすれば十分高速であるため、ソートや二分探索などの複雑な処理は不要。

## ソースコード

```python
import sys
from bisect import bisect_left

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

    # 選手Kのレーティング
    rating_K = S[K-1]
    
    # 選手Kよりレーティングが低い選手の数を数える
    count_lower = 0
    for s in S:
        if s < rating_K:
            count_lower += 1
    
    # 選手Kが勝てる相手の数が答え
    print(count_lower)

if __name__ == "__main__":
    main()

この解説は qwen3-coder-480b によって生成されました。