概要

地点 \(1\) から地点 \(N\) まで、毎回 \(+1\) または \(+2\) の移動をしながら進みます。
各地点で消耗し、補給食を得られる場合は回復できるので、リタイアせずに到達できる最大スタミナを動的計画法で求めます。

考察

この問題で重要なのは、補給食は手に入れたらすぐ食べてしまっても損をしないという点です。

スタミナには上限がありません。したがって、補給食を後で食べるよりも、今すぐ食べてスタミナを増やしておいた方が、以降の地点でリタイアしにくくなります。
また、最終的には地点 \(N\) に到達した後、残りの補給食をすべて食べた後のスタミナを最大化するので、途中で食べても最後に食べても、合計の回復量は変わりません。

そのため、各地点に到達した時点で、

1. その地点の消耗度 \(H_i\) だけスタミナを減らす
2. スタミナが \(0\) 未満なら失敗
3. 補給食があれば獲得し、その場ですぐ食べる

と考えて問題ありません。

---

素朴にすべての移動経路を試すと、各地点から \(+1\) または \(+2\) の選択があるため、経路数は指数的に増えます。
\(N\) は最大で \(10^6\) なので、全探索では間に合いません。

そこで、各地点 \(i\) について、

地点 \(i\) に到達し、その地点で補給食を食べ終えた後のスタミナの最大値

を管理します。

この値を \(dp[i]\) とします。

地点 \(i\) に来る直前の地点は、\(i-1\) または \(i-2\) のどちらかです。
したがって、\(dp[i-1]\) または \(dp[i-2]\) から遷移すればよいです。

ただし、地点 \(i\) に到達した瞬間に消耗度 \(H_i\) が引かれるので、到達前のスタミナが \(H_i\) 以上でなければなりません。

例えば、地点 \(i-1\) から来る場合は、

• \(dp[i-1] \geq H_i\) なら到達可能
• 到達後のスタミナは \(dp[i-1] - H_i\)
• その後、補給食があれば \(R_i\) 回復

なので、

\[ dp[i] = dp[i-1] - H_i + R_i \]

が候補になります。

同様に、地点 \(i-2\) から来る場合も考え、より大きい方を採用します。

アルゴリズム

まず、各地点にある補給食の回復量を配列 \(R\) に記録します。
補給食がない地点では \(R_i = 0\) とします。

\(dp[i]\) を次のように定義します。

\[ dp[i] = \text{地点 } i \text{ に到達し、補給食を食べ終えた後のスタミナの最大値} \]

到達不可能な場合は \(dp[i] = -1\) とします。

初期化

地点 \(1\) からスタートします。
最初に地点 \(1\) の消耗度 \(H_1\) を受けるので、

• \(K \geq H_1\) なら到達可能
• その後、補給食があれば回復する

したがって、

\[ dp[1] = K - H_1 + R_1 \]

です。

もし \(K < H_1\) なら、最初の地点でリタイアするため \(dp[1] = -1\) のままです。

遷移

地点 \(i\) について、直前の地点は \(i-1\) または \(i-2\) です。

地点 \(i-1\) から来る場合：

\[ dp[i-1] \geq H_i \]

なら到達可能で、

\[ dp[i] = \max(dp[i], dp[i-1] - H_i + R_i) \]

地点 \(i-2\) から来る場合：

\[ dp[i-2] \geq H_i \]

なら到達可能で、

\[ dp[i] = \max(dp[i], dp[i-2] - H_i + R_i) \]

最終的に \(dp[N]\) が答えです。
到達できない場合は \(dp[N] = -1\) になります。

計算量

• 時間計算量: \(O(N + M)\)
• 空間計算量: \(O(N)\)

実装のポイント

• 補給食の情報は、地点番号を添字にした配列 \(R\) に保存しておくと扱いやすいです。

• スタミナや消耗度、回復量は最大で \(10^9\) で、合計すると大きくなる可能性があるため、long long を使います。

• \(dp[i] = -1\) を「到達不可能」を表す値として使います。

• 地点 \(2\) は地点 \(0\) から来ることはできないため、\(i-2\) からの遷移は \(i \geq 3\) のときだけ行います。

  ソースコード

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;
    long long K;
    cin >> N >> M >> K;

    vector<long long> H(N + 1), R(N + 1, 0);
    for (int i = 1; i <= N; i++) cin >> H[i];

    for (int j = 0; j < M; j++) {
        int P;
        long long r;
        cin >> P >> r;
        R[P] = r;
    }

    vector<long long> dp(N + 1, -1);

    if (K >= H[1]) {
        dp[1] = K - H[1] + R[1];
    }

    for (int i = 2; i <= N; i++) {
        long long best = -1;

        if (dp[i - 1] >= H[i]) {
            best = max(best, dp[i - 1] - H[i] + R[i]);
        }

        if (i >= 3 && dp[i - 2] >= H[i]) {
            best = max(best, dp[i - 2] - H[i] + R[i]);
        }

        dp[i] = best;
    }

    cout << dp[N] << '\n';

    return 0;
}

---

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