概要

レーティングが高い方が必ず勝つトーナメントで、選手 \(K\) が最大で何勝できるかを求めます。結論として、答えは「\(K\) よりレーティングが低い選手の人数」です。

考察

この問題の重要ポイントは、トーナメントの「組み方を毎回自由に決められる」ことです。一般的な固定ブラケットのトーナメントだと、勝てる回数はおおむね \(O(\log N)\) に制限されそうですが、この問題では毎試合ごとに好きな 2 人を選んで戦わせられるため、選手 \(K\) に何度でも試合をさせられます（勝ち続ける限り）。

レーティングは全て異なり、強い方が必ず勝つので次が成り立ちます。

• 選手 \(K\) が勝てるのは、自分よりレーティングが低い相手に対してのみ。
  • よって勝利数の上限は「\(K\) より弱い選手の人数」。
• その上限は本当に達成可能。
  • 主催者は毎回、まだ残っている弱い選手がいれば、その弱い選手と \(K\) を戦わせればよい。
  • \(K\) は必ず勝ち、弱い選手が 1 人ずつ脱落していく。
  • 弱い選手を全員倒しきった時点で、残っているのは \(K\) と自分より強い選手だけなので、これ以上勝てない（強い相手に当たれば必ず負ける）。

したがって、最大勝利数は「\(K\) よりレーティングが低い選手の総数」に一致します。

具体例

\(S = [10, 30, 20, 40]\) で \(K\) のレーティングが \(30\) だとします。\(30\) より低いのは \(10, 20\) の 2 人なので答えは 2。 実際に、\(K\) を \(10\) と戦わせて勝つ → 次に \(20\) と戦わせて勝つ、で 2 勝できます。その後は \(40\) しか残らないので勝てません。

アルゴリズム

1. 選手 \(K\) のレーティングを \(r_K = S_K\) とする。
2. 全選手について \(S_i < r_K\) を満たす人数を数える。
3. その人数を出力する。

これは「\(K\) が勝てる相手の数」をそのまま数えているだけです。

計算量

• 時間計算量: \(O(N)\)（1 回走査して数えるだけ）
• 空間計算量: \(O(1)\)（入力配列を除けば定数）

実装のポイント

• \(K\) は 1-indexed で与えられるので、Python の配列では \(S[K-1]\) に注意します。

• 「\(K\) より小さい要素の個数」を単純に数えればよく、ソートなどは不要です。

  ソースコード

import sys

def main():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    S = list(map(int, input().split()))
    rk = S[K - 1]
    ans = sum(1 for x in S if x < rk)
    print(ans)

if __name__ == "__main__":
    main()

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