概要

各区間を順に走るたびに減るバッテリー残量を管理しつつ、途中の充電ステーションで「交換する／しない」を適切に選んで、最後まで到達できるかを判定する問題です。

考察

重要な気づき

充電ステーション \(j\) では、バッテリー残量を 任意の値に増やせる のではなく、ちょうど \(S_j\) にする 交換しかできません。
したがって、その場での最適な行動は非常に単純で、

• 現在残量が \(b\) のとき
  
  • \(S_j \le b\) なら交換するとむしろ減る（または同じ）ので 交換しないのが得
  • \(S_j > b\) なら交換で増えるので 交換するのが得

つまり、各ステーションでの最適行動は「\(b \leftarrow \max(b, S_j)\)」です。

なぜこの貪欲が正しいか

ステーションで交換するかどうかは、その後の走行可能性に影響しますが、交換した結果の残量は \(S_j\) に固定です。
したがって「交換する」ことは「残量を \(S_j\) に上書きする」だけであり、将来のために温存する・小出しに充電する、といった戦略は存在しません。

よって、その場で残量が増えるなら増やしておく（\(S_j>b\) なら交換）以外に得はなく、局所最適がそのまま全体最適になります。

素朴なアプローチが難しい点

「各ステーションで交換する/しないを全探索」すると、選択肢が最大 \(2^M\) 通りになり、\(M \le 2\times 10^5\) では到底間に合いません。
しかし上の観察により、各ステーションの判断は一意に決まり、単純なシミュレーションで十分になります。

アルゴリズム

1. 現在のバッテリー残量 \(b\) を \(K\) で初期化する。
2. 区間 \(i=1,2,\dots,N\) を順に処理する。
   • 区間を走る直前に \(b \ge 1\) でなければ走れないので No。
   • 区間 \(i\) を走って \(b \leftarrow b - D_i\)。
   • もし「区間 \(i\) と \(i+1\) の間」にステーションがある（つまり \(P_j=i\)）なら、
     • \(b \leftarrow \max(b, S_j)\)（増えるときだけ交換）
3. 最後まで処理できたら Yes。

位置の意味に注意すると、ステーション \(j\) は「区間 \(P_j\) を走り終えた直後（区間 \(P_j+1\) の直前）」に使えるため、\(D_{P_j}\) を引いた後で判定するのが正しいです。

例（イメージ）

• ある地点で \(b=3\)、次のステーションの \(S_j=10\) なら交換して \(b=10\) が得。
• 逆に \(b=8\)、\(S_j=5\) なら交換すると \(b=5\) になり損なので交換しない。

計算量

• 時間計算量: \(O(N+M)\)（区間を1回ずつ、ステーションもポインタで1回ずつ処理）
• 空間計算量: \(O(N+M)\)（入力保持。シミュレーション自体は \(O(1)\) 追加）

実装のポイント

• 「走行できる条件」は 走行直前に \(b \ge 1\) であること（走行後に \(0\) 以下になっても、その区間自体は走れた扱い）。

• ステーションは \(P_1 < P_2 < \cdots\) と昇順なので、ポインタ \(j\) を進めながら P[j] == i を見れば \(O(N+M)\) で処理できる。

• ステーション処理のタイミングは \(b -= D[i-1]\) の後（区間 \(i\) の直後）に置く。

  ソースコード

import sys

def main():
    it = iter(map(int, sys.stdin.buffer.read().split()))
    N = next(it)
    M = next(it)
    K = next(it)

    D = [next(it) for _ in range(N)]
    P = [0] * M
    S = [0] * M
    for j in range(M):
        P[j] = next(it)
        S[j] = next(it)

    b = K
    j = 0
    for i in range(1, N + 1):
        if b < 1:
            print("No")
            return
        b -= D[i - 1]
        if j < M and P[j] == i:
            if S[j] > b:
                b = S[j]
            j += 1

    print("Yes")

if __name__ == "__main__":
    main()

---

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