概要

スタート地点からゴール地点まで、\(+1\) または \(+2\) の移動で進みながら、各地点での消耗に耐えてゴールに到達できるかを判定し、到達可能なら最終スタミナの最大値を求める問題です。経路選択と補給食の使用タイミングを最適化する DP（動的計画法）で解きます。

考察

補給食はすぐに食べるのが最適

この問題の最も重要な気づきは、手に入れた補給食はその場ですべて食べてしまうのが常に最適だということです。

理由は次の通りです。

• スタミナに上限がない（初期値 \(K\) を超えてもよい）
• 補給食を持ち越しても食べても、後で食べられる総量は変わらない
• リタイア判定は「消耗直後にスタミナが \(0\) 未満か」で行われる

つまり、補給食を早く食べるほどスタミナが高くなり、その後のリタイア判定を通過しやすくなります。逆に持ち越して食べるのを遅らせても、得することは一切ありません。したがって「入手した瞬間に全部食べる」と固定してよいのです。

この観察により、「どの補給食をいつ食べるか」という指数的な選択の問題が消え、考えるべきは経路（\(+1\) か \(+2\) か）だけになります。

各地点での状態を考える

ある地点 \(i\) に到達して処理（消耗 → 判定 → 入手 → 食べる）を終えたときのスタミナを \(dp[i]\) とします。

• 地点 \(i\) に来る直前のスタミナ（＝直前の地点での処理後のスタミナ）を \(s\) とすると、消耗後は \(s - H_i\)
• リタイアしない条件は \(s - H_i \geq 0\)、すなわち \(s \geq H_i\)
• 通過できれば、補給食 \(food_i\) を入手・即座に食べて、\(dp[i] = s - H_i + food_i\)

地点 \(i\) には地点 \(i-1\) または \(i-2\) から来られるので、\(s\) の候補は \(dp[i-1]\) と \(dp[i-2]\) です。

素朴なアプローチの問題点

すべての経路を列挙すると経路数は指数的になり、また「どの補給食を食べるか」を全探索すると \(2^M\) 通りになって到底間に合いません。\(N\) が最大 \(10^6\) あるため、線形時間の DP が必要です。上記の「すぐ食べる」観察と DP の組み合わせでこれを解決します。

アルゴリズム

\(dp[i]\) を「地点 \(i\) で処理を終えた直後の最大スタミナ」とし、到達不可能なら未定義（コードでは \(-1\)）とします。

初期化（地点 \(1\)）

\[ dp[1] = \begin{cases} K - H_1 + food_1 & (K - H_1 \geq 0) \\ \text{到達不可} & (\text{それ以外}) \end{cases} \]

遷移（\(i \geq 2\)）

地点 \(i-1\) または \(i-2\) のうち、到達可能かつ \(dp[\cdot] \geq H_i\) を満たすものの中で最大の値を \(best\) とします。

\[ dp[i] = best - H_i + food_i \quad (best \geq H_i \text{ のとき}） \]

満たすものが無ければ地点 \(i\) は到達不可です。

ここで予め最大の \(best\) を選んでよいのは、最終スタミナを最大化するためであり、また「より多いスタミナ」が後続の判定でも有利だからです。

答え

\(dp[N]\) が到達可能ならその値を、そうでなければ \(-1\) を出力します。

具体例での確認

たとえば地点 \(i\) の手前で \(dp[i-1] = 5\)、\(dp[i-2] = 8\)、\(H_i = 6\) のとき、\(dp[i-1]=5 < 6\) なので \(i-1\) からは消耗に耐えられずリタイアします。一方 \(dp[i-2]=8 \geq 6\) なので \(i-2\) から来れば通過でき、\(dp[i] = 8 - 6 + food_i\) となります。このように「より大きい方かつ条件を満たす方」を選びます。

計算量

• 時間計算量: \(O(N + M)\)
  • DP は各地点を一度だけ見るので \(O(N)\)、補給食の読み込みが \(O(M)\)。
• 空間計算量: \(O(N)\)
  • 配列 dp、H、food を保持するため。

実装のポイント

• 到達可能な \(dp\) の値は必ず \(0\) 以上になります。そこで「未到達」を表す値を \(-1\)（NEG）にしておくと、\(H_i \geq 0\) より「未到達のセルが遷移条件 dp[pred] >= H_i を誤って満たす」ことが起こらず、特別な分岐なしで安全に判定できます。

• \(N\) が最大 \(10^6\) と大きいため、入力は sys.stdin.buffer.read() でまとめて読み込み、高速に処理します。

• 補給食は地点ごとに高々 \(1\) 個なので、food[p] = r という配列で地点と回復量を対応づけると扱いやすくなります。

  ソースコード

import sys

def main():
    data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(data[idx]); idx += 1
    M = int(data[idx]); idx += 1
    K = int(data[idx]); idx += 1
    H = [0] * (N + 1)
    for i in range(1, N + 1):
        H[i] = int(data[idx]); idx += 1
    food = [0] * (N + 1)
    for _ in range(M):
        p = int(data[idx]); idx += 1
        r = int(data[idx]); idx += 1
        food[p] = r

    NEG = -1  # unreachable (reachable dp values are always >= 0)
    dp = [NEG] * (N + 1)

    if K - H[1] >= 0:
        dp[1] = K - H[1] + food[1]

    for i in range(2, N + 1):
        hi = H[i]
        best = NEG
        # from i-1
        v = dp[i - 1]
        if v >= hi:
            best = v
        # from i-2
        if i - 2 >= 1:
            v = dp[i - 2]
            if v >= hi and v > best:
                best = v
        if best >= hi:  # best != NEG and best >= hi (hi>=0 so NEG=-1 fails)
            dp[i] = best - hi + food[i]

    print(dp[N] if dp[N] >= 0 else -1)

main()

---

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