概要

辞退者を除外した候補者の中で、得点が高い順に上位\(K\)人が合格となる場合に、高橋君が合格できるかを判定する問題です。

考察

問題を解くためには、辞退者を除外した候補者リストを作成し、その中で高橋君が上位\(K\)人に含まれているかを確認する必要があります。素朴なアプローチとして、すべての候補者をソートしてから辞退者を除外すると、ソート順が崩れて正しい順位が計算できなくなる可能性があります。また、辞退者を除外した後にソートすると、ソートの対象が\(N-M\)人となるため効率的です。

重要な点は、ソートの条件が「得点が高い順、同じ得点なら番号が小さい順」であることです。高橋君の番号は1なので、同じ得点の場合には有利になります。

アルゴリズム

1. 入力データを読み込む
2. 辞退者の集合を作成する
3. 辞退者を除外した候補者リストを作成する（各要素は(得点, 番号)のタプル）
4. 作成したリストを「得点の降順、番号の昇順」でソートする
5. ソートしたリストの先頭から\(K\)人を調べ、高橋君（番号1）が見つかれば”Yes”、見つからなければ”No”を出力する

計算量

• 時間計算量: \(O(N \log N)\)
  • ソートが支配的で、\(N\)最大200,000なので十分高速
• 空間計算量: \(O(N)\)
  • 辞退者集合と残りの候補者リストを保持するため

実装のポイント

• 辞退者の管理には集合型(set)を使用して、存在確認を\(O(1)\)で行えるようにする

• ソートのキーとして(-得点, 番号)を使用することで、得点の降順と番号の昇順を一度に指定できる

• 高橋君が見つかった時点で即時返却することで、無駄な処理を省く

• \(M=0\)の場合の入力処理に注意する（3行目が存在しない可能性がある）

  ソースコード

import sys

def main():
    data = sys.stdin.read().split()
    if not data:
        print("No")
        return
        
    n = int(data[0])
    k = int(data[1])
    m = int(data[2])
    scores = list(map(int, data[3:3+n]))
    if m > 0:
        dropouts = set(map(int, data[3+n:3+n+m]))
    else:
        dropouts = set()
    
    # 高橋君の得点
    takahashi_score = scores[0]
    
    # 辞退者を除いた候補者を集計
    remaining = []
    for i in range(n):
        candidate_id = i + 1
        if candidate_id not in dropouts:
            remaining.append((scores[i], candidate_id))
    
    # 得点が高い順、同じ得点なら番号が小さい順にソート
    remaining.sort(key=lambda x: (-x[0], x[1]))
    
    # 上位K人の中に高橋君がいるか確認
    count = 0
    for score, candidate_id in remaining:
        count += 1
        if candidate_id == 1:
            print("Yes")
            return
        if count >= k:
            break
            
    print("No")

if __name__ == "__main__":
    main()

この解説は deepseekv3 によって生成されました。