概要

\(N\) 人の候補者の中から、辞退者を除いた残りのメンバーで上位 \(K\) 人に入るかどうかを判定する問題です。高橋君は候補者番号 \(1\) であり、得点の高さ、次いで番号の小ささで順位が決まります。

考察

合格条件を整理すると、以下のようになります。 1. 得点が高い人が上位。 2. 得点が同じなら、番号が小さい人が上位。

高橋君（番号 \(1\) ）に注目すると、他の候補者 \(i\) (\(i > 1\)) と比較したとき、番号は必ず高橋君の方が小さいです。したがって、タイブレークのルールにより、得点が同じ場合は必ず高橋君が上位になります。

つまり、高橋君より順位が上になるのは、以下の条件を両方満たす候補者のみです。 - 辞退していない。 - 高橋君より高い得点を持っている（ \(S_i > S_1\) ）。

高橋君の順位は「（自分より順位が上の人数） + 1」で決まるため、辞退者を除いた中で \(S_i > S_1\) を満たす人数をカウントし、その値が \(K-1\) 以下であれば、高橋君は \(K\) 位以内に入り合格できることになります。

アルゴリズム

1. 入力から \(N, K, M\) および各候補者の得点 \(S_i\) を受け取る。
2. 辞退者のリスト \(D\) を元に、各候補者が辞退したかどうかを判定できる配列（またはセット）を作成する。
3. 高橋君の得点 \(S_1\) を基準として、以下の条件を満たす候補者の数 better_than_takahashi を数える。
   • 候補者の番号 \(i\) が \(2\) 以上 \(N\) 以下である。
   • 候補者 \(i\) が辞退していない。
   • \(S_i > S_1\) である。
4. better_than_takahashi + 1 <= K であれば Yes、そうでなければ No を出力する。

計算量

• 時間計算量: \(O(N)\)
  • 入力の読み込みに \(O(N)\)、辞退者のマークに \(O(M)\)、得点の比較に \(O(N)\) かかります。\(M \le N\) であるため、全体で \(O(N)\) となり、制約の \(N = 2 \times 10^5\) に対して十分高速に動作します。
• 空間計算量: \(O(N)\)
  • 得点リストや辞退判定用の配列を保持するために \(O(N)\) のメモリを使用します。

実装のポイント

• タイブレークの処理: 高橋君の番号が最小（1）であるため、S[i] == S[1] のケースを考慮する必要がなく、単純に S[i] > S[1] だけをチェックすれば良い点がポイントです。

• 高速な入力: \(N\) が大きいため、Python の場合は sys.stdin.read().split() などを用いて一括で入力を取得すると効率的です。

• 辞退者の管理: 辞退者かどうかの判定を高速に行うために、ブール値の配列やハッシュセットを使用します。

  ソースコード

import sys

def solve():
    # Read all input at once and split into tokens for efficient processing
    try:
        input_data = sys.stdin.read().split()
    except EOFError:
        return
    
    if not input_data:
        return
    
    # N: total number of candidates
    # K: number of candidates who will pass
    # M: number of candidates who withdrew
    n = int(input_data[0])
    k = int(input_data[1])
    m = int(input_data[2])
    
    # Candidate 1 is Takahashi. His score is S_1.
    # Scores are given as S_1, S_2, ..., S_N starting from input_data[3].
    s1 = int(input_data[3])
    
    # Mark which candidates have withdrawn using a boolean array.
    # Candidate IDs are 1-indexed (from 1 to N).
    # M can be 0, in which case the withdrawn list will remain all False.
    is_withdrawn = [False] * (n + 1)
    if m > 0:
        # Withdrawn candidate IDs D_1, ..., D_M follow the N scores in the input.
        for i in range(m):
            d_id = int(input_data[3 + n + i])
            is_withdrawn[d_id] = True
            
    # Count how many remaining candidates are ranked strictly higher than Takahashi.
    # According to the rules:
    # 1. Higher score is better.
    # 2. If scores are equal, the smaller candidate ID is better.
    # Since Takahashi is candidate 1, any other candidate i (where i > 1) 
    # can only be ranked higher than Takahashi if their score S_i is strictly greater than S_1.
    better_than_takahashi = 0
    for i in range(2, n + 1):
        if not is_withdrawn[i]:
            # The score S_i for candidate i is located at input_data[3 + i - 1]
            si = int(input_data[3 + i - 1])
            if si > s1:
                better_than_takahashi += 1
                
    # Takahashi's rank among the remaining candidates is (better_than_takahashi + 1).
    # He passes if his rank is less than or equal to K.
    if better_than_takahashi + 1 <= k:
        print("Yes")
    else:
        print("No")

if __name__ == '__main__':
    solve()

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