概要

初期スキルレベル \(S\) から始めて、難易度 \(D_i\) の問題を解くことでスキルを上げ、目標の \(T\) 以上に到達できるかを判定する問題です。

考察

この問題の核心は、「どの順番で問題を解くのが最適か？」という点にあります。

高橋君が問題を解くためには、現在のスキルレベルがその問題の難易度以上である必要があります。問題を解くとスキルレベルが上昇するため、解けば解くほど「次に解ける問題の選択肢」は増えていきます。

ここで、難しい問題から先に解こうとするメリットはありません。なぜなら、難しい問題を解くためには高いスキルが必要ですが、簡単な問題を先に解いてスキルを底上げしておけば、後でその難しい問題を解けるようになる可能性が高まるからです。

したがって、「現在解ける問題の中で、最も難易度が低いものから順番に解いていく」という貪欲な戦略が最適となります。難易度が低い順にソートして順番に確認し、もし現在のスキルで解けない問題にぶつかったら、それ以降の（さらに難易度が高い）問題も絶対に解けないため、そこで探索を終了できます。

アルゴリズム

以下の手順で判定を行います。

1. 初期スキルレベル \(S\) がすでに目標 \(T\) 以上であれば、即座に Yes を出力して終了します。
2. 与えられた問題の難易度リスト \(D\) を昇順（小さい順）にソートします。
3. ソートされた難易度を一つずつ取り出し、以下の処理を繰り返します。
   • 現在のスキルレベル \(\ge\) 取り出した難易度 \(D_i\) であれば、問題を解いてスキルレベルに \(D_i\) を加算します。
   • 加算後のスキルレベルが \(T\) 以上になったら、Yes を出力して終了します。
   • もし現在のスキルレベルよりも難易度 \(D_i\) の方が大きければ、その問題もそれ以降の問題も解けないため、ループを抜けます。
4. 最後までループが回っても \(T\) に達しなかった場合は、No を出力します。

計算量

• 時間計算量: \(O(N \log N)\)
  • \(N\) 個の要素のソートに \(O(N \log N)\) かかります。その後のリストの走査は \(O(N)\) なので、全体ではソートの計算量が支配的になります。
  • 今回の制約 \(N \leq 2 \times 10^5\) では、この計算量で十分に間に合います。
• 空間計算量: \(O(N)\)
  • \(N\) 個の問題の難易度を保持するための配列（リスト）に \(O(N)\) のメモリを使用します。

実装のポイント

• 早期終了: 初期状態で \(S \ge T\) の場合や、途中で \(T\) を超えた場合にすぐに Yes を出力することで、無駄な計算を省けます。

• ソートの利用: sorted() 関数や .sort() メソッドを使って難易度を並び替えることが、この問題を解くための最も重要なステップです。

• 大きな数値の扱い: \(S\) や \(T\) が最大 \(10^{18}\) という非常に大きな値になる可能性があるため、言語によってはオーバーフローに注意が必要ですが、Pythonでは標準で多倍長整数を扱えるため、そのまま計算して問題ありません。

  ソースコード

import sys

def main():
    # 入力を一度に読み込み、空白で分割してリスト化します
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N: 問題数, S: 初期スキルレベル, T: 目標スキルレベル
    n = int(input_data[0])
    s = int(input_data[1])
    t = int(input_data[2])
    
    # すでに目標スキルレベルに達している場合
    if s >= t:
        print("Yes")
        return
    
    # 各問題の難易度を整数に変換し、昇順にソートします（貪欲法）
    # 難易度の低い問題から解くことで、より多くの問題を解ける可能性が高まります
    d_list = sorted(map(int, input_data[3:]))
    
    current_skill = s
    for d in d_list:
        # 現在のスキルレベルで解ける問題か判定
        if current_skill >= d:
            # スキルレベルを問題の難易度分だけ上昇させる
            current_skill += d
            # 目標スキルレベルに達したか判定
            if current_skill >= t:
                print("Yes")
                return
        else:
            # 難易度順に並んでいるため、現在のスキルで解けない問題が現れたら
            # それ以降の全ての問題も解くことができません
            break
    
    # 全ての問題を検討しても目標に達しなかった場合
    print("No")

if __name__ == '__main__':
    main()

この解説は gemini-3-flash-preview によって生成されました。