概要

基地からゴールまでの直線上を進むとき、各ステーションで「可能な限り充電する」ことを繰り返したときのゴール到達可否と、到達時の残量最大値を求めます。

考察

重要な気づき

この問題には一見「どのステーションでどれだけ充電するか」という選択がありそうですが、残量最大化のためには各ステーションで充電できるだけ充電するのが常に最適です。

理由は次の通りです。

• ステーション到着時の残量を \(e\)、充電量を \(w\) とすると、充電後の残量は
  \(f(e)=\min(C, e+w)\)
  です。
• この \(f(e)\) は \(e\) が大きいほど結果も小さくならない（単調増加） という性質があります。
• また、移動は距離 \(d\) だけ進むと残量が \(e-d\) になるだけなので、これも \(e\) が大きいほど有利です。

つまり「今の残量を大きくしておく」ことは、将来の残量を減らす方向には働きません（上限 \(C\) で頭打ちになるだけ）。

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

「各ステーションで何ユニット充電するか」を全探索やDPで考えると、 - 充電量 \(W_i\) や容量 \(C\) が最大 \(10^9\) と大きく、状態数を持てない - \(N\) も最大 \(2\times 10^5\) ある
ため、計算量的に現実的ではありません。

そこで、最適行動が一意（毎回満タンまで充電）であることを利用して、単純なシミュレーションで解けます。

到達不能判定も同時にできる

「常に最大まで充電する」戦略は、各地点で到達可能な残量を最大化します。
したがって、この戦略で次の地点まで届かない（残量が距離未満）なら、他のどんな戦略でもそれ以上の残量にはできないため、到達不可能です。

アルゴリズム

1. 初期残量を \(e=C\)、直前位置を prev=0 とする。
2. ステーションを前から順に処理する（位置は昇順で与えられる）。
   • 前の地点からの距離 \(d = P_i - prev\) を計算
   • もし \(e < d\) なら途中で止まるので -1
   • 移動して \(e \leftarrow e-d\)
   • 充電して \(e \leftarrow \min(C, e + W_i)\)
   • prev = P_i
3. 最後にゴールまでの距離 \(d=L-prev\) について同様にチェックして移動する。
4. ゴール到達時の残量 \(e\) を出力する。

（例）
容量 \(C=10\)、残量 \(e=3\) の状態で \(w=9\) を充電すると
\(e \leftarrow \min(10, 3+9)=10\) となり、溢れた分は捨てられます。

計算量

• 時間計算量: \(O(N)\)（各ステーションを1回ずつ処理）
• 空間計算量: \(O(1)\)（現在残量と位置など定数個のみ）

実装のポイント

• ステーション間・ゴールまでの距離は「前回位置との差」で計算する（prev を更新する）。

• 各区間で必ず e < d をチェックして、届かない時点で即 -1 を出力する。

• 充電は必ず e = min(C, e + w) のように容量でクリップする。

  ソースコード

import sys

def main():
    input = sys.stdin.readline
    L, N, C = map(int, input().split())
    e = C
    prev = 0

    for _ in range(N):
        p, w = map(int, input().split())
        d = p - prev
        if e < d:
            print(-1)
            return
        e -= d
        e = min(C, e + w)
        prev = p

    d = L - prev
    if e < d:
        print(-1)
        return
    e -= d
    print(e)

if __name__ == "__main__":
    main()

---

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