概要

「現在のスキル以下の問題しか解けない」という制約のもとで、問題をうまく選んで解き、最終スキルを \(T\) 以上にできるかを判定します。

考察

重要な観察は次の2つです。

• 解ける問題の中では、難易度が小さいものから解くのが安全（むしろ最善）

  • どの問題を解いてもスキルは増えますが、解くためには「今のスキル以上でないといけない」という条件があります。
  • したがって、まずは今解ける問題のうち一番簡単なものを解けば、確実にスキルが増えて次に解ける範囲が広がります。
  • 逆に、解ける問題が複数あるのに大きいものを先に選んでも得はなく、「小さいものを後回しにする理由」がありません。

• 昇順ソートして見ていき、途中で詰まったらそれ以降は絶対に解けない

  • 難易度を昇順に並べて、左から順に「解けるなら解く」を繰り返します。
  • もしある時点で \(d > \text{cur}\)（今のスキル）となったら、昇順なのでそれ以降の問題はすべて \(d' \ge d > \text{cur}\) です。
  • よって 残りのどの問題も解けず、これ以上スキルは上がらないことが確定します。

素朴に「解ける問題を毎回探して選ぶ」「全探索する」などをすると、 - 全探索は \(2^N\) で不可能 - 「毎回解ける最大を探す」などの方針は正当性が保証できない（WAの原因） - データ構造で頑張っても結局やりたいことは「解けるものを小さい順に処理」なので、最初にソートして一回なめるのが最も簡潔で確実です。

具体例： - \(S=10\), 問題 \([1, 9, 20]\) - 昇順で解く：\(10 \to 11\)（1）\(\to 20\)（9）で 20 に到達し、20 の問題も解けるようになる - 途中で「解けない問題」が出たら、その先も解けないので打ち切れます

アルゴリズム

1. 難易度配列 \(D\) を昇順にソートする。
2. 現在スキル \(\text{cur}=S\) とする。最初から \(\text{cur} \ge T\) なら Yes。
3. ソート済みの各 \(d\) について順に：
   • もし \(d > \text{cur}\) なら、これ以降も解けないのでループを終了。
   • そうでなければ解けるので \(\text{cur} \leftarrow \text{cur} + d\)。
   • \(\text{cur} \ge T\) になったら Yes。
4. 最後まで到達できなければ No。

この方法は「小さいものから解いていけば、解ける限りスキルを最大限伸ばせる」ため、到達可能性の判定として正しいです。

計算量

• 時間計算量: \(O(N \log N)\)（ソートが支配的）
• 空間計算量: \(O(N)\)（配列保持）

実装のポイント

• \(S,T\) は最大 \(10^{18}\) なので、言語によっては 64bit整数が必要（Python は int が多倍長なので問題なし）。

• ソート後は1回の走査でよいので、\(d > \text{cur}\) になったら 即座に break してよい（昇順だから）。

• 途中で \(\text{cur} \ge T\) に達したら 早期終了すると高速です。

  ソースコード

import sys

def main():
    input = sys.stdin.readline
    N, S, T = map(int, input().split())
    D = list(map(int, input().split()))
    D.sort()

    cur = S
    if cur >= T:
        print("Yes")
        return

    for d in D:
        if d > cur:
            break
        cur += d
        if cur >= T:
            print("Yes")
            return

    print("Yes" if cur >= T else "No")

if __name__ == "__main__":
    main()

この解説は gpt-5.2-high によって生成されました。