概要

初期スキルレベル \(S\) からスタートし、解ける問題（難易度が現在のスキル以下）を解いてスキルを上げていき、目標スキルレベル \(T\) に到達できるかを判定する問題です。

考察

重要な気づき

1. 解ける問題の条件: 難易度 \(D_i\) が現在のスキルレベル以下のとき、その問題を解ける
2. スキルの成長: 問題を解くと、その難易度の分だけスキルが上昇する
3. 各問題は1回まで: 同じ問題を何度も解くことはできない

貪欲法が最適である理由

「解ける問題があれば、どの順番で解いても最終的なスキルの増加量は同じ」という性質があります。

例えば、スキル \(S = 5\) で、難易度 \(3\) と \(4\) の問題がどちらも解ける場合： - \(3 → 4\) の順：\(5 → 8 → 12\) - \(4 → 3\) の順：\(5 → 9 → 12\)

どちらも最終スキルは同じです。

しかし、難易度の低い問題から順に解くことが重要です。なぜなら、スキルが低い段階では難易度の高い問題は解けないからです。

例：スキル \(S = 5\)、難易度 \(6, 3\) の問題がある場合 - 難易度 \(6\) は最初は解けない（\(6 > 5\)） - 難易度 \(3\) を先に解く：\(5 → 8\) - すると難易度 \(6\) が解ける：\(8 → 14\)

なぜソートして順番に見るだけでよいか

難易度を昇順にソートして、解ける問題を順番に解いていけば、「解けるはずの問題を見逃す」ことがありません。難易度 \(d\) の問題が解けるなら、それより難易度が低い問題は必ず既に解いた後だからです。

アルゴリズム

1. 難易度の配列 \(D\) を昇順にソートする
2. 現在のスキル current_skill を \(S\) で初期化する
3. ソートされた難易度を順番に見ていく：
   • もし current_skill >= T なら、目標達成なので終了
   • もし難易度 \(d\) が current_skill 以下なら、その問題を解いて current_skill += d
4. ループ終了後、current_skill >= T なら Yes、そうでなければ No

例: N=3, S=5, T=15, D=[6, 3, 8]
ソート後: D=[3, 6, 8]

current_skill = 5
- d=3: 3 <= 5 なので解く → current_skill = 8
- d=6: 6 <= 8 なので解く → current_skill = 14
- d=8: 8 <= 14 なので解く → current_skill = 22

22 >= 15 なので「Yes」

計算量

• 時間計算量: \(O(N \log N)\)
  • ソートに \(O(N \log N)\)
  • ループは \(O(N)\)
• 空間計算量: \(O(N)\)
  • 難易度の配列を格納するため

実装のポイント

1. ソートを忘れない: 難易度の低い問題から順に見ることが、貪欲法が正しく動作するために必須

2. オーバーフローに注意: \(S, T\) が最大 \(10^{18}\) と非常に大きいが、Pythonでは整数のオーバーフローは起きないので問題なし（C++などでは注意が必要）

3. 早期終了: 目標達成したらすぐにループを抜けることで、無駄な計算を省ける（なくても正しく動作する）

   ソースコード

def solve():
    N, S, T = map(int, input().split())
    D = list(map(int, input().split()))
    
    # 難易度でソート
    D.sort()
    
    current_skill = S
    
    # 貪欲に解ける問題を解いていく
    for d in D:
        if current_skill >= T:
            break
        if d <= current_skill:
            current_skill += d
    
    if current_skill >= T:
        print("Yes")
    else:
        print("No")

solve()

---

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