概要

トーナメントの対戦組み合わせを自由に決められるとき、応援している選手 \(K\) が最大で何回勝利できるかを求める問題です。レーティングが高い方が必ず勝つため、選手 \(K\) は自分よりレーティングが低い選手にのみ勝てます。

考察

重要な気づき①：勝敗は完全に決まっている

すべての選手のレーティングは異なり、レーティングが大きい方が必ず勝つため、任意の2選手の対戦結果は事前に確定しています。選手 \(K\) は、自分よりレーティングが低い選手には必ず勝ち、高い選手には必ず負けます。

重要な気づき②：対戦順序は自由に決められる

各ラウンドで残っている選手の中から任意の2人を選べるため、選手 \(K\) を誰と戦わせるかは完全にコントロールできます。これはトーナメントブラケットが固定されている通常のトーナメントとは異なります。

重要な気づき③：弱い選手がいる限り、Kは勝ち続けられる

選手 \(K\) より弱い選手（レーティングが低い選手）が残っている限り、高橋君は選手 \(K\) をその弱い選手と戦わせることができます。選手 \(K\) は必ず勝ち、次のラウンドに進めます。

• 選手 \(K\) が最強（レーティング最大）の場合：全員に勝てるので、答えは \(N - 1\) です。
• そうでない場合：自分より弱い選手を1人ずつ倒していけます。弱い選手が全員いなくなったら、残っているのは自分より強い選手だけなので、次の試合で必ず負けます。

具体例

\(N = 5, K = 3, S = [10, 30, 20, 50, 40]\) の場合：

• 選手 \(3\) のレーティングは \(20\)
• 弱い選手：選手 \(1\)（レーティング \(10\)）→ 1人
• 強い選手：選手 \(2, 4, 5\)（レーティング \(30, 50, 40\)）→ 3人

高橋君は選手 \(3\) と選手 \(1\) を戦わせ、選手 \(3\) が勝利。その後は強い選手しか残っていないので、選手 \(3\) は負けます。答えは 1 です。

アルゴリズム

1. 選手 \(K\) のレーティング \(S_K\) を取得する。
2. \(S_K\) より小さいレーティングを持つ選手の数（\(\text{num\_weaker}\)）を数える。
3. \(S_K\) より大きいレーティングを持つ選手の数（\(\text{num\_stronger}\)）を数える。
4. \(\text{num\_stronger} = 0\)（選手 \(K\) が最強）なら、答えは \(N - 1\)。
5. そうでなければ、答えは \(\text{num\_weaker}\)。

計算量

• 時間計算量: \(O(N)\)（全選手のレーティングを1回走査して数えるだけ）
• 空間計算量: \(O(N)\)（入力の格納）

実装のポイント

• 選手番号は \(1\)-indexed なので、配列アクセス時に S[K-1] とする必要があります。

• 選手 \(K\) が最強かどうかの場合分けを忘れないようにしましょう。最強の場合は全 \(N-1\) 試合に勝てます。

• ソートは解法の本質には不要で、単に \(S_K\) より小さい要素の個数を数えれば十分です。

  ソースコード

import sys

def solve():
    input_data = sys.stdin.read().split()
    N = int(input_data[0])
    K = int(input_data[1])
    S = list(map(int, input_data[2:2+N]))
    
    sk = S[K-1]
    
    # Count how many players have rating less than sk
    # Player K can beat all players with rating < sk
    # The question is: how many of them can K actually face in an optimal tournament?
    
    # Players weaker than K (K can beat them)
    weaker = sorted([s for s in S if s < sk])
    # Players stronger than K (K loses to them)
    stronger = sorted([s for s in S if s > sk])
    
    num_weaker = len(weaker)
    num_stronger = len(stronger)
    
    # Strategy: We want K to fight as many weaker players as possible before
    # eventually facing a stronger player (if any).
    # 
    # But we also need to "eliminate" stronger players by having them fight each other
    # or fight weaker players, so that K doesn't have to face them.
    # Wait, K will eventually lose to a stronger player (or win the tournament if K is strongest).
    
    # If K is the strongest player, K can win N-1 times (fight everyone one by one).
    if num_stronger == 0:
        print(N - 1)
        return
    
    # K can beat all weaker players. The question is how many weaker players
    # can K face before being forced to face a stronger player.
    #
    # At each round, we choose any two remaining players to fight.
    # We want to maximize K's wins.
    #
    # Strategy: Have K fight weaker players one by one. Meanwhile, we need
    # to also eliminate other players (stronger ones can fight each other or 
    # fight weaker ones) but we need to keep enough weaker players for K to fight.
    #
    # Total N players, N-1 matches total. K will play some matches, winning against
    # weaker opponents, and eventually lose to a stronger opponent (or never face one
    # if we can eliminate all stronger players - but we can't since K can't beat them
    # and stronger players can only be eliminated by even stronger players).
    #
    # Actually, we need all stronger players to be eliminated by other stronger players
    # or... no. The tournament ends when 1 player remains. K will be eliminated when
    # K faces a stronger player. We want to delay this as long as possible.
    #
    # We can have K fight one weaker player each round while having stronger players
    # fight each other (or fight weaker players) in other matches.
    #
    # Each round we can have multiple matches? No - "each round" we pick 2 players
    # for 1 match. So rounds are sequential, one match per round.
    #
    # So in each round, we pick 2 players. We can alternate: have K fight a weaker
    # player, then have two other players fight, then K fights another weaker player, etc.
    #
    # K needs to fight weaker players. Each time K fights, that uses one round and 
    # eliminates one weaker player. We can also use rounds to have other players 
    # fight each other (not involving K) to reduce the total count.
    #
    # K will eventually need to face a stronger player (since stronger players exist
    # and the tournament must end with 1 player). K loses that match.
    #
    # We want to maximize the number of K's wins. K can fight a weaker player 
    # whenever there's at least one weaker player remaining. K loses when forced
    # to face a stronger player.
    #
    # But K is never "forced" to face a stronger player as long as weaker players exist.
    # So K can keep fighting weaker players until no weaker players remain.
    # Then K must face a stronger player and lose.
    #
    # So the answer is simply: number of weaker players = num_weaker.
    # 
    # Wait, but we need other matches to happen too to keep the tournament going.
    # Actually no - we just freely choose who fights whom each round. As long as
    # there are weaker players, we can always have K fight one of them. 
    # K wins, the weaker player is eliminated, and we continue.
    # When no weaker players remain, K faces a stronger player and loses.
    
    print(num_weaker)

solve()

---

この解説は claude4.6opus-thinking によって生成されました。