概要

高橋君がスタミナを管理しながら地点 \(1\) から地点 \(N\) まで移動し、途中でスタミナが \(0\) 未満にならずにゴールできるかを判定し、可能な場合は最終スタミナの最大値を求める問題です。

考察

この問題を解くための重要なポイントは「補給食をいつ食べるか」という点です。 問題文では「補給食は後で食べてもよい」とありますが、実は「手に入れた瞬間にすべての補給食を食べる」と仮定しても、最終的なスタミナの最大値や途中でリタイアするかどうかの判定に影響を与えないことが分かります。

なぜなら、補給食を温存して後で食べても、スタミナの総量は同じです。また、スタミナが足りずリタイアしそうなときに補給食を食べるのであれば、それは「過去の地点で手に入れた瞬間に食べておく」ことと全く同じ状態になるからです。つまり、各地点で手に入れた補給食はその場で即座にすべて消費すると考えて問題ありません。

この観察に基づき、次のような動的計画法（DP）を考えます。 - DPの状態: T[i] = 地点 \(i\) に到達し、リタイア判定を通り、地点 \(i\) で手に入れた補給食をすべて食べ終えた状態でのスタミナの最大値。到達不可能な場合は \(-1\) とする。

もし全探索で移動経路や補給食を食べるタイミングを調べようとすると、組み合わせが爆発的に増えてTLE（時間切れ）になります。しかし、上記のように「即時消費」を仮定することで、状態を「地点 \(i\) における最大スタミナ」の1変数に削減でき、高速に計算できるようになります。

アルゴリズム

配るDPを用いて地点 \(1\) から順に計算していきます。

1. 初期状態: 地点 \(1\) に到達できるのは、初期スタミナ \(K\) が地点 \(1\) の消耗度 \(H_1\) 以上のときです。 したがって、\(K \ge H_1\) ならば \(T[1] = K - H_1 + R_1\) とします（\(R_i\) は地点 \(i\) にある補給食の回復量、なければ \(0\)）。

2. 遷移: 地点 \(i\) (\(1 \le i < N\)) に到達している場合（\(T[i] \ne -1\)）、以下の2つの移動を試みます。

   • 地点 \(i+1\) への移動: \(T[i] \ge H_{i+1}\) であればリタイアせずに到達できます。到達後のスタミナは \(T[i] - H_{i+1} + R_{i+1}\) となるので、これで \(T[i+1]\) を更新します（最大値をとる）。
   • 地点 \(i+2\) への移動: \(T[i] \ge H_{i+2}\) であればリタイアせずに到達できます。到達後のスタミナは \(T[i] - H_{i+2} + R_{i+2}\) となるので、これで \(T[i+2]\) を更新します。

3. 答え: 最終的に \(T[N]\) が地点 \(N\) に到達後かつ手持ちの補給食をすべて食べ終えた状態の最大スタミナとなります。\(T[N] = -1\) であれば到達不可能なので \(-1\) を出力します。

計算量

• 時間計算量: \(O(N)\) 各地点 \(i\) から遷移するのは \(i+1\) と \(i+2\) の2箇所のみであり、全体で線形時間で計算できます。
• 空間計算量: \(O(N)\) 配列 \(T, H, R\) のサイズが \(N\) に比例します。

実装のポイント

• 制約より \(N \le 10^6\)、\(H_i, R_i \le 10^9\) であるため、スタミナの計算途中で \(10^{15}\) 程度の値になる可能性があり、32bit整数（int）ではオーバーフローします。そのため、スタミナ関連の変数は64bit整数（C++では long long）を必ず使用してください。

• \(M\) 個の補給食の情報を管理する際、地点ごとに高々1つしかないため、R[p] = r のように地点のインデックスに直接回復量を格納する配列を用意すると実装がシンプルになります。

• 入力が大きいため、std::cin の高速化（ios::sync_with_stdio(false); cin.tie(nullptr);）を行うと安心です。

  ソースコード

#include <iostream>
#include <vector>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int N, M;
    long long K;
    if (!(cin >> N >> M >> K)) return 0;
    
    vector<long long> H(N + 1, 0);
    vector<long long> R(N + 1, 0);
    
    for (int i = 1; i <= N; ++i) {
        cin >> H[i];
    }
    
    for (int i = 0; i < M; ++i) {
        int p;
        long long r;
        cin >> p >> r;
        R[p] = r;
    }
    
    vector<long long> T(N + 1, -1);
    if (K >= H[1]) {
        T[1] = K - H[1] + R[1];
    }
    
    for (int i = 1; i < N; ++i) {
        if (T[i] == -1) continue;
        
        if (i + 1 <= N && T[i] >= H[i + 1]) {
            long long val = T[i] - H[i + 1] + R[i + 1];
            if (val > T[i + 1]) {
                T[i + 1] = val;
            }
        }
        
        if (i + 2 <= N && T[i] >= H[i + 2]) {
            long long val = T[i] - H[i + 2] + R[i + 2];
            if (val > T[i + 2]) {
                T[i + 2] = val;
            }
        }
    }
    
    cout << T[N] << "\n";
    return 0;
}

この解説は or-glm5.2-high によって生成されました。