概要

高橋君はスキルレベル \(S\) から始めて、難易度の問題を解いてスキルを上げ、目標レベル \(T\) 以上にしたい。解けるのは現在のスキル以下の問題だけで、各問題は一度だけ解ける。目標達成ができるか判定せよ。

考察

この問題では、貪欲法（greedy）の考え方が重要になります。

重要な観察

• 高橋君は、現在のスキルレベル以下の問題しか解けない。
• 解くことでスキルが上がり、さらに多くの問題が解けるようになる。
• なるべく早く目標 \(T\) に到達するには、「今解ける中で一番難しい問題」を選ぶのが最適。

素朴なアプローチの問題点

たとえば、毎回「今解ける問題の中で一番難しいもの」を線形探索で探すと、計算量が \(O(N^2)\) になり、\(N\) が最大 \(2 \times 10^5\) の制約では間に合いません。

解決方法

そこで、以下の工夫をします： 1. 問題の難易度をソートしておき、スキルが上がったときに順番に追加できるようにする。 2. 「今解ける問題の中で一番難しいもの」を高速に取り出すために、優先度付きキュー（ヒープ）を使う。 - 最大値を取り出すには、Pythonでは最小ヒープしかないので、負の値を入れて管理します。

これにより、効率的に貪欲な選択が可能になります。

アルゴリズム

1. 問題の難易度リスト \(D\) を昇順にソートする。
2. 現在のスキルレベル \(current\_skill = S\) で初期化。
3. 解ける問題をヒープに追加しながら、以下の処理を行う：
   • \(current\_skill < T\) の間繰り返す。
   • \(D\) を順に見ていき、難易度が \(current\_skill\) 以下のものをヒープに追加（負にして）。
   • ヒープが空なら、解ける問題がないので No を出力。
   • そうでなければ、ヒープから最も難しい問題（最大の難易度）を取り出して解く。
   • スキルを更新：\(current\_skill += difficulty\)
4. ループを抜けたら、目標達成しているので Yes を出力。

具体例

入力：

N=3, S=2, T=10
D = [3, 5, 7]

• スキル2 → 解けるのは難易度3の問題。
• 解くとスキル5 → 次に難易度5の問題が解ける。
• 解くとスキル10 → 目標達成！

→ Yes

計算量

• 時間計算量: \(O(N \log N)\)
  • ソートに \(O(N \log N)\)
  • ヒープ操作が最大 \(N\) 回、各操作が \(O(\log N)\)
• 空間計算量: \(O(N)\)
  • ヒープに最大 \(N\) 個格納される

実装のポイント

• Pythonの heapq は最小ヒープなので、最大値を取り出すときは要素を負にして管理する。

• 問題の難易度をソートしておくことで、順番にヒープに追加できる。

• ヒープが空なのに問題が欲しくなるケース（解ける問題がないのに目標未達）には注意して No を出力。

  ソースコード

import heapq

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    N = int(data[0])
    S = int(data[1])
    T = int(data[2])
    D = list(map(int, data[3:]))

    # 最小ヒープとして使用するため、負の値で管理
    heap = []
    current_skill = S
    index = 0

    # 問題の難易度をソートしておく
    D.sort()

    while current_skill < T:
        # 解ける問題をヒープに追加（負の値で）
        while index < N and D[index] <= current_skill:
            heapq.heappush(heap, -D[index])
            index += 1
        
        # 解ける問題がない場合、終了
        if not heap:
            print("No")
            return
        
        # 最も難しい問題（最も大きい難易度）を選ぶ
        max_difficulty = -heapq.heappop(heap)
        current_skill += max_difficulty
    
    print("Yes")

if __name__ == "__main__":
    main()

---

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