概要

辞退者を除いた上位 \(K\) 人に候補者 \(1\)（高橋君）が入るかを、順位のルール（同点なら番号が小さい方が上）を踏まえて判定します。

考察

重要なのは「高橋君（番号 \(1\)）より上に来る可能性がある人は誰か」を正しく数えることです。

順位は「得点が高い順、同点なら番号が小さい順」です。ここで高橋君の番号は最小の \(1\) なので、

• 他人の得点が 高橋君より大きい なら、その人は必ず高橋君より上
• 他人の得点が 高橋君と同点 でも、番号は必ず \(1\) より大きいので高橋君の方が上（＝その人は高橋君より上には来ない）
• 他人の得点が 低い なら当然高橋君より下

つまり、高橋君の合否に影響するのは 「辞退していない人の中で、高橋君より得点が高い人数」 だけです。
この人数が \(K\) 人以上いると、高橋君は上位 \(K\) 人に入れません。

素朴に「辞退者を除いた全員を並べ替えて上位 \(K\) を作る」方法でも解けますが、並べ替えは \(O(N\log N)\) で、条件次第では不要に重いです。この問題は上の観察により、並べ替え不要で \(O(N)\) で判定できます。

（具体例）
\(K=3\)、高橋君の得点が \(80\) のとき、辞退者を除いて「得点が \(80\) より高い人」が 2 人なら高橋君は 3 位以内に入れますが、3 人いるなら 4 位以下になり不合格です。

アルゴリズム

1. 高橋君の得点 \(s_1 = S_1\) を取得する。
2. 辞退者番号 \(D_j\) を集合 withdrawn に入れて、辞退者判定を高速化する。
3. 候補者 \(i=2\) から \(N\) までについて：
   • \(i\) が辞退者なら無視する
   • \(S_i > s_1\) なら「高橋君より上の人数」better を 1 増やす
4. better \le K-1 なら高橋君は上位 \(K\) に入れるので Yes、そうでなければ No。

同点の扱いについては、番号 \(1\) が最小なので「\(S_i = s_1\) の人は高橋君より上に来ない」→「比較は \(>\) のみでよい」という点がポイントです。

計算量

• 時間計算量: \(O(N+M)\)（辞退者集合の構築が \(O(M)\)、全候補者の走査が \(O(N)\)）
• 空間計算量: \(O(M)\)（辞退者集合）

実装のポイント

• 辞退者の判定を毎回線形探索すると遅くなるため、set にして \(O(1)\) 平均で判定します。

• \(M=0\) のときは 3 行目が存在しないため、入力を読む際に M>0 の場合だけ辞退者を読むようにします。

• 同点処理は不要で、条件は S_i > S_1 のみで十分です（高橋君の番号が \(1\) だから）。

  ソースコード

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    it = iter(data)

    N = next(it)
    K = next(it)
    M = next(it)

    S = [next(it) for _ in range(N)]
    withdrawn = set(next(it) for _ in range(M)) if M > 0 else set()

    s1 = S[0]
    better = 0
    for i in range(2, N + 1):
        if i in withdrawn:
            continue
        if S[i - 1] > s1:
            better += 1

    print("Yes" if better <= K - 1 else "No")

if __name__ == "__main__":
    main()

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