概要

ロボットが一直線のルート上を基地からゴールまで進む際、途中のエネルギーステーションで充電しながら、ゴール到達時のバッテリー残量を最大化する問題です。すべてのステーションは順番に通過するため、シミュレーションで解くことができます。

考察

重要な気づき：充電は常に行うべき

この問題で最も重要な観察は、エネルギーステーションでの充電にデメリットがないという点です。

• ステーションはルート上にあるため、ロボットは必ず通過します（迂回のコストがない）。
• 充電するとバッテリーが増える（またはバッテリー容量 \(C\) で頭打ちになる）だけで、減ることはありません。
• したがって、すべてのステーションで必ず充電するのが最適です。

選択の余地がない → シミュレーション

「どのステーションで充電するか」という選択問題に見えますが、上記の理由からすべてのステーションで充電するのが最適です。つまり、基地からゴールまで順番にシミュレーションするだけで答えが求まります。

具体例で確認

例えば \(L = 20, N = 2, C = 10\) で、ステーションが \((5, 8)\) と \((15, 3)\) の場合：

1. 基地出発: バッテリー \(= 10\)
2. 位置5に到着: バッテリー \(= 10 - 5 = 5\)、充電後 \(= \min(5 + 8, 10) = 10\)
3. 位置15に到着: バッテリー \(= 10 - 10 = 0\)、充電後 \(= \min(0 + 3, 10) = 3\)
4. ゴール（位置20）に到着: バッテリー \(= 3 - 5 = -2 < 0\) → 到達不可、-1 を出力

アルゴリズム

1. バッテリーを \(C\)（満充電）に初期化し、現在位置を \(0\)（基地）とする。
2. 各エネルギーステーションを順番に処理する：
   • 現在位置からステーションまでの距離分、バッテリーを減らす。
   • バッテリーが負になったら -1 を出力して終了（途中で停止）。
   • 充電量を加算し、バッテリー容量 \(C\) を超えないように min を取る。
3. 最後のステーション（またはステーションがなければ基地）からゴールまでの距離分、バッテリーを減らす。
4. バッテリーが負なら -1、そうでなければバッテリー残量を出力する。

計算量

• 時間計算量: \(O(N)\) — 各ステーションを1回ずつ処理するだけ
• 空間計算量: \(O(N)\) — ステーション情報の格納（逐次読み込みにすれば \(O(1)\) も可能）

実装のポイント

• オーバーフローに注意: \(L\) や \(C\) が最大 \(10^9\) ですが、Python では整数のオーバーフローがないため特に問題ありません。C++ などの言語では long long を使う必要があります。

• ステーションが0個の場合: ステーションがない場合、\(C \geq L\) ならバッテリー残量は \(C - L\)、そうでなければ -1 です。ループが実行されないだけで正しく処理されます。

• 充電のキャップ: min(battery + w, C) で、バッテリー容量を超えないように制限することを忘れないようにしましょう。この制限があるため、早い段階で充電しすぎても「溢れる」分は無駄になりますが、充電しない理由にはなりません（充電しても損はしないため）。

  ソースコード

import sys

def solve():
    input_data = sys.stdin.read().split()
    idx = 0
    L = int(input_data[idx]); idx += 1
    N = int(input_data[idx]); idx += 1
    C = int(input_data[idx]); idx += 1
    
    stations = []
    for i in range(N):
        p = int(input_data[idx]); idx += 1
        w = int(input_data[idx]); idx += 1
        stations.append((p, w))
    
    # Start with full battery C, consume distance to move, charge at stations (capped at C)
    # This is a straightforward simulation since we must visit all stations in order
    # (there's no choice to skip - we always pass through them, and charging is always beneficial)
    
    # Wait - is charging always beneficial? Yes, because charging increases or maintains battery,
    # and we want to maximize remaining battery at the end. There's no downside to charging.
    
    battery = C
    prev_pos = 0
    
    for p, w in stations:
        dist = p - prev_pos
        battery -= dist
        if battery < 0:
            print(-1)
            return
        battery = min(battery + w, C)
        prev_pos = p
    
    # Travel from last station to goal
    dist = L - prev_pos
    battery -= dist
    if battery < 0:
        print(-1)
        return
    
    print(battery)

solve()

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