概要

地点 \(1\)（麓）からスタートし、スタミナを \(0\) 未満にすることなく移動を繰り返して地点 \(N\)（山頂）へ到達可能かを判定し、到達可能な場合の最終的な最大スタミナを求める問題です。

考察

1. 補給食を食べるタイミングの最適化

問題文には「補給食は手持ちにして後で食べることもできる」とありますが、補給食は手に入れた瞬間にすべて食べてしまうのが常に最適です。

理由は以下の通りです。 - スタミナの値に上限はありません。 - 補給食を後まで温存しておいても、最終的な回復量の合計は変わりません。 - むしろ、手に入れた段階で即座に食べてスタミナを増やしておくことで、道中の地点で「消耗によってスタミナが \(0\) 未満になりリタイアする」という事態を最も防ぎやすくなります。

したがって、「各地点に到達してリタイア判定を通過した直後に、その地点にある補給食をすべて食べる」という戦略をとるのが最適です。

2. 動的計画法（DP）の適用

高橋君は地点 \(i\) から \(i+1\) または \(i+2\) にのみ移動できます。これは典型的な「足場をジャンプする」タイプの問題であり、動的計画法（DP）を用いて解くことができます。

状態を以下のように定義します。 - dp[i] : 地点 \(i\) に到達し、その地点の補給食を食べ終えた時点でのスタミナの最大値（到達不可能な場合は \(-1\)）

初期状態

地点 \(1\) での消耗を引いたスタミナが \(0\) 以上であれば、そこから補給食 \(R_1\) を食べることができます。 - \(K - H_1 \geq 0\) のとき： dp[1] = K - H[1] + R[1] - \(K - H_1 < 0\) のとき： dp[1] = -1 （スタート時点でリタイア）

遷移

地点 \(i\) から移動するとき、 dp[i] != -1 であれば、次の地点 \(next \in \{i+1, i+2\}\) に対して以下のように遷移します。 1. 地点 \(next\) に移動した直後のスタミナは dp[i] - H[next] になります。 2. これが \(0\) 以上であればリタイアせずに到達可能です。 3. 到達できた場合、地点 \(next\) の補給食 \(R_{next}\) を食べるため、スタミナは dp[i] - H[next] + R[next] に更新されます。 4. dp[next] をこの値の最大値で更新します。 $\(\text{dp}[next] = \max(\text{dp}[next], \text{dp}[i] - H[next] + R[next])\)$

アルゴリズム

1. 各地点の消耗度 \(H\) と、補給食の回復量 \(R\) を配列に格納します（補給食がない地点は \(0\) とします）。
2. DPテーブル dp をサイズ \(N+1\)、初期値 \(-1\) で作成します。
3. 地点 \(1\) の初期化を行います。
4. \(i = 1\) から \(N-1\) まで順にループを回し、 dp[i] から dp[i+1] および dp[i+2] への遷移を行います。
5. 最終的な答えは dp[N] となります（到達不可能な場合は自動的に -1 が出力されます）。

計算量

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

  • 入力の受け取りに \(O(N + M)\) かかります。
  • DPの遷移は、各地点 \(i\) から定数個（最大2個）の遷移先を探索するため、全体で \(O(N)\) です。
  • したがって、全体として \(O(N + M)\) で動作し、 \(N \le 10^6\) の制約下でも十分高速に実行可能です。

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

  • 各地点の情報を管理する配列 H, R および DPテーブル dp のサイズはすべて \(N + 1\) です。
  • したがって、空間計算量は \(O(N)\) となり、メモリ制限にも余裕で収まります。

実装のポイント

• オーバーフローの防止: 初期スタミナ \(K\) や回復量 \(R_j\) は最大で \(10^9\) であり、これらが累積するとスタミナの最大値は \(32\) ビット整数（int型）の上限を超えてしまいます。そのため、スタミナを管理する変数や配列はすべて long long 型を使用する必要があります。

• 高速入出力: \(N, M\) の値が大きいため、C++では cin.tie(NULL); ios_base::sync_with_stdio(false); を用いて入出力を高速化しています。

  ソースコード

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    // 高速入出力
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, M;
    long long K;
    if (!(cin >> N >> M >> K)) return 0;

    vector<long long> H(N + 1);
    for (int i = 1; i <= N; ++i) {
        cin >> H[i];
    }

    vector<long long> R(N + 1, 0);
    for (int j = 0; j < M; ++j) {
        int P;
        long long val;
        cin >> P >> val;
        R[P] = val;
    }

    // dp[i] は地点 i に到達し、補給食を食べた後のスタミナの最大値
    // 到達不可能な場合は -1
    vector<long long> dp(N + 1, -1);

    // スタート地点での処理
    if (K - H[1] >= 0) {
        dp[1] = K - H[1] + R[1];
    }

    for (int i = 1; i < N; ++i) {
        if (dp[i] == -1) continue;

        // 地点 i + 1 への移動
        if (i + 1 <= N) {
            if (dp[i] - H[i + 1] >= 0) {
                dp[i + 1] = max(dp[i + 1], dp[i] - H[i + 1] + R[i + 1]);
            }
        }

        // 地点 i + 2 への移動
        if (i + 2 <= N) {
            if (dp[i] - H[i + 2] >= 0) {
                dp[i + 2] = max(dp[i + 2], dp[i] - H[i + 2] + R[i + 2]);
            }
        }
    }

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

    return 0;
}

---

この解説は gemini-3.5-flash-high によって生成されました。