概要

辞退者がいる中で、高橋君（番号 \(1\)）がオーケストラのオーディションに合格するかどうかを判定する問題です。

考察

この問題では、候補者全員の得点が与えられ、その中で辞退者が指定されています。辞退者を除いた残りの人々について、得点の高い順に上位 \(K\) 人が合格となります。ただし、得点が同じ場合は番号が小さい方を優先します。

素朴な方法として、毎回ソートして上位 \(K\) 人を選ぶことを考えますが、候補者数 \(N\) が最大で \(2 \times 10^5\) なので、効率的な処理が必要です。

ポイントは以下の通りです： - 辞退者を集合（set）で管理することで、高速に除外判定を行う - 得点の比較に加えて、番号も比較条件に含めるため、ソートキーを適切に設定する

得点が同じ場合に番号順に並べる必要があるため、単純に得点だけでソートするのではなく、得点降順、かつ番号昇順にする必要があります。

アルゴリズム

1. 入力を読み込み、辞退者の番号をセット（set）に格納しておく（高速な検索のため）。
2. 辞退していない候補者について、(番号, 得点) のタプルをリストに保存。
3. このリストを以下のようにソート：
   • 得点が高い順（降順）
   • 得点が同じなら、番号が小さい順（昇順）
4. ソート後に上位 \(K\) 人の番号を取得し、その中に高橋君（番号 \(1\)）が含まれているかを判定。

例えば、以下の入力があったとします：

N=5, K=2, M=1
S = [80, 90, 80, 70, 90]
D = [3]

このとき、辞退しない候補者は番号 1, 2, 4, 5 で、それぞれの得点は [80, 90, 70, 90] です。
タプルにすると：

[(1, 80), (2, 90), (4, 70), (5, 90)]

これを得点降順・番号昇順でソートすると：

[(2, 90), (5, 90), (1, 80), (4, 70)]

上位2人は番号 2 と 5 なので、高橋君（番号1）は不合格 → “No” が出力されます。

計算量

• 時間計算量: \(O(N \log N)\) （ソートが支配的）
• 空間計算量: \(O(N)\) （候補者のリストやセットの管理）

実装のポイント

• 入力を高速に読み込むために sys.stdin.read を使用している
• 辞退者の判定を高速に行うために set を使う（リストだと線形時間になってしまう）
• ソートキーを (得点, -番号) ではなく (-得点, 番号) とすることで、得点降順・番号昇順を自然に表現できる

## ソースコード

```python
import sys
input = sys.stdin.read

def main():
    data = input().split()
    N = int(data[0])
    K = int(data[1])
    M = int(data[2])
    
    S = list(map(int, data[3:3+N]))
    
    if M == 0:
        D_set = set()
    else:
        D_set = set(map(int, data[3+N:3+N+M]))
    
    # 辞退しない候補者のリストを作成 (番号, 得点) のタプル
    candidates = []
    for i in range(1, N+1):
        if i not in D_set:
            candidates.append((i, S[i-1]))
    
    # ソート: 得点降順、番号昇順
    candidates.sort(key=lambda x: (-x[1], x[0]))
    
    # 上位K人の番号を取得
    top_k = set(candidate[0] for candidate in candidates[:K])
    
    # 高橋君（番号1）が上位K人に含まれるか判定
    if 1 in top_k:
        print("Yes")
    else:
        print("No")

if __name__ == "__main__":
    main()

---

この解説は qwen3-coder-480b によって生成されました。