概要

\(N\) 個のステージについてそれぞれクリアするかどうかを選択し、「クリアしたステージの得点 \(A_i\)」と「連続してクリアしたことによるボーナス \(C\)」の合計を最大化する問題です。 直前のステージをクリアしたかどうかに着目することで、動的計画法（DP）を用いて \(O(N)\) で解くことができます。

考察

素朴なアプローチ

各ステージについて「クリアする」「クリアしない」の \(2\) 通りの選択肢があるため、すべての選び方を探索すると \(2^N\) 通りになります。 \(N \le 10^6\) であるため、全探索を行うと実行時間制限に到底間に合いません（TLEとなります）。

問題を解くための重要な気づき

ステージ \(i\) をクリアするかどうかを決めるとき、スコアに影響を与える過去の情報は「直前のステージ \(i - 1\) をクリアしたかどうか」のみです。 - ステージ \(i - 1\) をクリアしていない場合：ステージ \(i\) をクリアすると得られるスコアは \(A_i\) です。 - ステージ \(i - 1\) をクリアしていた場合：ステージ \(i\) をクリアすると得られるスコアは \(A_i + C\)（コンボボーナスが発生）になります。

ステージ \(i - 2\) 以前の選択結果は、ステージ \(i\) でのボーナスの発生有無には直接関与しません。 したがって、「ステージ \(i\) まで見たときの、直前の状態に応じた最大スコア」を順に記録していく動的計画法（DP）が有効です。

アルゴリズム

以下のように DP テーブルを定義します。

• dp0: 現在のステージをクリアしなかった場合のスコアの最大値
• dp1: 現在のステージをクリアした場合のスコアの最大値

ステージを \(1\) つ進めるごとに、次のように状態を更新します（現在のステージの得点を \(A\) とします）。

1. 次のステージをクリアしない場合 (next_dp0)

   • 直前のステージをクリアしていてもしていなくてもクリアしない選択が可能です。スコアは変化しません。
   • next_dp0 = max(dp0, dp1)

2. 次のステージをクリアする場合 (next_dp1)

   • 直前のステージをクリアしていなかった場合、スコアは \(+A\) されます（dp0 + A）。
   • 直前のステージをクリアしていた場合、ボーナス \(C\) も付与されるためスコアは \(+A + C\) されます（dp1 + A + C）。
   • next_dp1 = max(dp0 + A, dp1 + A + C)

初期値と答え

• 開始時点（ステージ \(0\) まで終了したとみなす）では：
  • 何もクリアしていない状態: dp0 = 0
  • クリアした状態は存在しないため、あり得ない状態として十分に小さい値（\(-\infty\)）で初期化: dp1 = -INF
• ステージ \(N\) までの更新が終わった後、max(dp0, dp1) が求める最大スコアとなります（1つもクリアしない場合、スコア \(0\) となることも考慮されています）。

計算量

• 時間計算量: \(O(N)\)
  • 各ステージについての更新は \(O(1)\) で行われます。ステージ数は \(N\) 個であるため、全体で \(O(N)\) となり、実行時間制限内に十分間に合います。
• 空間計算量: \(O(1)\)
  • 直前の状態（dp0 と dp1）のみを保持しながら入力をその都度処理するため、追加の配列を保持する必要がなく \(O(1)\) で済みます。

実装のポイント

• オーバーフローへの注意:

  • 得点 \(A_i\) やボーナス \(C\) は最大で \(10^9\) であり、\(N = 10^6\) のため、最大スコアは \(10^6 \times 2 \times 10^9 \approx 2 \times 10^{15}\) に達します。

  • これは 32-bit 符号付き整数の上限（約 \(2 \times 10^9\)）を大きく超えるため、必ず 64-bit 整数型（C++ の long long）を使用してください。

  • 未到達状態を表す \(-\infty\) にも、オーバーフローを起こさず十分に小さい値（例: \(4 \times 10^{18}\) など）を設定する必要があります。

    ソースコード

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

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    long long c;
    if (!(cin >> n >> c)) return 0;

    const long long INF = 4e18;
    long long dp0 = 0;
    long long dp1 = -INF;

    for (int i = 0; i < n; ++i) {
        long long a;
        cin >> a;
        long long next_dp0 = max(dp0, dp1);
        long long next_dp1 = max(dp0 + a, dp1 + a + c);
        dp0 = next_dp0;
        dp1 = next_dp1;
    }

    cout << max(dp0, dp1) << "\n";

    return 0;
}

---

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