概要

\(N\) 人の選手が参加するトーナメントにおいて、対戦カードを自由に決められるとき、特定の選手 \(K\) が最大で何回勝利できるかを求める問題です。試合では常にレーティングが高い方が勝利します。

考察

この問題を解くための重要なポイントは、「選手 \(K\) が勝てる相手は誰か」、そして「その相手とどのように対戦を組めばよいか」を考えることです。

1. 選手 \(K\) が勝てる条件

問題文より、試合ではレーティングが大きい方の選手が必ず勝利します。したがって、選手 \(K\) がある試合で勝利するためには、対戦相手のレーティングが \(S_K\) 未満である必要があります。逆に、レーティングが \(S_K\) より高い選手と当たってしまうと、選手 \(K\) はその時点で必ず負けて脱落してしまいます。

2. 最大勝利数を達成する戦略

選手 \(K\) の勝利数を最大化するためには、「選手 \(K\) が勝てる相手（自分よりレーティングが低い人）全員と、一人ずつ順番に戦わせる」という戦略が有効です。

例えば、選手 \(K\) よりレーティングが低い選手が \(m\) 人いるとします。 1. まず、選手 \(K\) と「自分より低いレーティングを持つ選手 A」を戦わせます。選手 \(K\) が勝利し、勝利数は 1 になります。 2. 次に、勝ち残った選手 \(K\) と「自分より低いレーティングを持つ別の選手 B」を戦わせます。選手 \(K\) が勝利し、勝利数は 2 になります。 3. これを \(m\) 回繰り返すことで、選手 \(K\) は \(m\) 回勝利することができます。

3. 自分より強い選手はどうするか？

自分よりレーティングが高い選手が残っていると、選手 \(K\) が負けてしまう可能性があります。しかし、トーナメントの組み方は自由なので、「自分より強い選手同士を先に戦わせて、一人を除いて全員脱落させる」ことができます。最後に残った最強の選手と選手 \(K\) が当たって負けたとしても、それまでに自分より弱い選手全員に勝っていれば、勝利数は最大化されます。

以上の考察から、選手 \(K\) の最大勝利数は「全選手のうち、選手 \(K\) よりもレーティングが低い人の人数」に一致することがわかります。

アルゴリズム

1. 選手 \(K\) のレーティング \(S_K\) を取得します。
2. 全ての選手 \(i = 1, 2, \ldots, N\) について、そのレーティング \(S_i\) を確認します。
3. \(S_i < S_K\) を満たす選手の数をカウントします。
4. カウントした値を答えとして出力します。

計算量

• 時間計算量: \(O(N)\)
  • 選手全員のレーティングを 1 回ずつ確認するため、人数 \(N\) に比例した時間で計算が終わります。\(N=10^5\) なので、十分に高速です。
• 空間計算量: \(O(N)\)
  • 全選手のレーティングをリストに格納する場合、メモリ空間は \(N\) に比例します。

実装のポイント

• 選手の番号 \(K\) は 1-indexed（1から始まる）で与えられることが多いですが、プログラミング言語（Pythonなど）のリストは 0-indexed（0から始まる）であることが多いため、インデックスの扱いに注意してください（選手 \(K\) のレーティングは S[K-1] で取得できます）。

• \(S_i\) はすべて異なると問題文にあるため、自分自身（選手 \(K\)）との比較を厳密に除外する必要はありません（\(S_K < S_K\) は常に偽となるため）。

  ソースコード

import sys

# The problem asks for the maximum number of matches player K can win.
# In a tournament where Takahashi can freely decide the pairings,
# player K can win a match against any player with a lower rating.
# Let m be the number of players whose rating is less than player K's rating.
# Each match player K wins must be against one of these m players.
# Since each player is eliminated after losing once, player K can win at most m matches.
# Takahashi can achieve this maximum by having player K face each of these m players
# one by one in the first m matches. Any players with ratings higher than player K
# can be paired with each other until only one remains, whom player K will eventually
# face and lose to (unless player K is already the overall winner).

def solve():
    # Read all input from standard input at once for efficiency.
    input_data = sys.stdin.read().split()
    if len(input_data) < 2:
        return
    
    # N: total number of players
    # K: the index of the player Takahashi supports (1-indexed)
    n = int(input_data[0])
    k = int(input_data[1])
    
    # S: list of ratings of all N players.
    # Ratings are provided as S1, S2, ..., SN.
    # In Python's 0-indexed list, player K's rating is at index K-1.
    s = list(map(int, input_data[2:2+n]))
    
    # Get the rating of player K.
    target_rating = s[k-1]
    
    # Count how many players have a rating strictly less than target_rating.
    # Every such player represents a potential win for player K.
    max_wins = 0
    for rating in s:
        if rating < target_rating:
            max_wins += 1
            
    # Output the result.
    print(max_wins)

if __name__ == '__main__':
    solve()

---

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