概要

辞退者を除いた候補者の中で、得点順に上位 \(K\) 人を選び、高橋君（候補者 \(1\)）がその中に含まれるかを判定する問題です。

考察

この問題で重要なポイントは以下の通りです。

1. 辞退者の除外: まず辞退した候補者を候補から取り除く必要があります。辞退者の番号が与えられるので、集合（set）に格納しておけば \(O(1)\) で辞退者かどうかを判定できます。

2. 同点時のルール: 得点が同じ場合は「番号が小さい候補者が上位」となります。高橋君は番号 \(1\) なので、同点の候補者がいる場合は最も有利な立場にあります。

3. ソートによる順位付け: 辞退者を除いた候補者を「得点が高い順、同点なら番号が小さい順」に並べ替えれば、先頭から \(K\) 人が合格者です。

素朴なアプローチでも、\(N\) 人の候補者をソートするだけなので \(O(N \log N)\) で十分高速に解けます。特別な高速化は不要です。

アルゴリズム

1. 辞退者の番号を集合 withdrawn に格納する。
2. 候補者 \(1\) から \(N\) のうち、辞退していない候補者だけを抽出する。
3. 抽出した候補者を 得点の降順 でソートする。得点が同じ場合は 番号の昇順 でソートする。
   • 実装上は、各候補者を \((-S_i, i)\) というタプルにして昇順ソートすると、得点が大きいほど先に来て、同点なら番号が小さいほど先に来ます。
4. ソート後の先頭 \(K\) 人の中に、番号 \(1\)（高橋君）がいれば Yes、いなければ No を出力する。

具体例

候補者が 5 人、得点が \([80, 90, 80, 70, 85]\)、\(K=3\)、辞退者なしの場合：

タプルを昇順ソートすると：\((-90, 2), (-85, 5), (-80, 1), (-80, 3), (-70, 4)\)

上位 \(3\) 人は候補者 \(2, 5, 1\) → 高橋君（候補者 \(1\)）は含まれるので Yes。

同点の候補者 \(1\) と \(3\) では、番号が小さい \(1\) が上位になっている点がポイントです。

計算量

• 時間計算量: \(O(N \log N)\)（候補者のソートが支配的）
• 空間計算量: \(O(N)\)（候補者リストと辞退者集合の格納）

実装のポイント

• 辞退者の高速判定: 辞退者の番号を set に格納することで、各候補者が辞退したかどうかを \(O(1)\) で判定できます。

• ソートキーの工夫: Python のタプルは先頭要素から辞書順で比較されるため、\((-S_i, \text{番号})\) とすれば一回の sort() で「得点降順・番号昇順」を同時に実現できます。得点にマイナスを付けるテクニックは競技プログラミングでよく使われます。

• \(M = 0\) の場合: 辞退者がいない場合、3 行目が存在しません。sys.stdin.read().split() でまとめて読み込めば、この場合でも特別な処理は不要です。

  ソースコード

import sys

def main():
    input_data = sys.stdin.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    K = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    S = [int(input_data[idx + i]) for i in range(N)]
    idx += N
    withdrawn = set()
    for i in range(M):
        withdrawn.add(int(input_data[idx + i]))
    
    # Build list of (score, number) for non-withdrawn candidates
    # Sort by (-score, number) so higher score first, then smaller number first
    candidates = []
    for i in range(N):
        num = i + 1
        if num not in withdrawn:
            candidates.append((-S[i], num))
    
    candidates.sort()
    
    # Top K candidates pass
    for i in range(K):
        if candidates[i][1] == 1:
            print("Yes")
            return
    
    print("No")

main()

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