概要

\(N\) 個のステージから任意の部分集合を選び、「選んだステージの \(A_i\) の総和」＋「隣接して選んだペアの個数 \(\times C\)」を最大化する問題です。直前のステージを選んだかどうかを状態に持つ簡単な区間 DP（bit DP 的な線形 DP）で解けます。

考察

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

「すべてのクリアパターンを試す」と、\(2^N\) 通りの選び方があります。\(N \le 10^6\) なので当然間に合いません。

貪欲は通用するか？

「\(A_i > 0\) のステージだけ選ぶ」という貪欲は誤りです。例えば

N=3, C=10
A = 5, -3, 5

\(A_i>0\) のみ選ぶと \(5+5=10\) ですが、ステージ \(2\) も選ぶと \(5-3+5+2\times 10 = 27\) となり、負のステージを「橋渡し」として選んだ方が得になります。逆に \(C=0\) なら負のステージを選ぶ意味はありません。つまり「その 1 つのステージ単体の得点」だけでは判断できず、前後の選択状況に依存するのがこの問題の本質です。

重要な気づき

スコアの増分に注目します。ステージ \(i\) を選ぶとき、加算されるのは

• \(A_i\)（必ず）
• ステージ \(i-1\) も選んでいれば、さらに \(C\)

だけです。つまり「1 つ前のステージを選んだか否か」さえ分かっていれば、次のステージの得点は確定するわけです。それより前の情報（どのステージを選んだか）は一切必要ありません。

したがって「先頭から順に決めていく」DP で、状態は「直前を選んだ／選んでいない」の 2 通りだけで済みます。

アルゴリズム

\(i\) 番目まで処理した時点での値を次の 2 つで管理します。

• \(dp[i][0]\) : ステージ \(i\) を選ばなかった場合の、ステージ \(1..i\) までで得られる最大スコア
• \(dp[i][1]\) : ステージ \(i\) を選んだ場合の、ステージ \(1..i\) までで得られる最大スコア

遷移は以下の通りです。

• \(dp[i][0] = \max(dp[i-1][0],\; dp[i-1][1])\)
  • ステージ \(i\) を選ばないのでスコアは増えず、ボーナスも発生しない。直前はどちらでもよい。
• \(dp[i][1] = \max(dp[i-1][0],\; dp[i-1][1] + C) + A_i\)
  • ステージ \(i\) を選ぶので \(A_i\) を加算。さらに直前も選んでいた場合のみボーナス \(C\) が付く。

初期状態は「まだ 0 個処理した状態」として \(dp[0][0]=0\)、\(dp[0][1]=-\infty\)（ステージ 0 は存在しないので「選んだ」状態はあり得ない）とします。

答えは \(\max(dp[N][0], dp[N][1])\) です。

具体例（\(N=3, C=10, A=(5,-3,5)\)）

\(i\)	\(A_i\)	\(dp[i][0]\)	\(dp[i][1]\)
0	-	0	\(-\infty\)
1	5	0	\(\max(0,-\infty)+5=5\)
2	-3	\(\max(0,5)=5\)	\(\max(0,5+10)-3=12\)
3	5	\(\max(5,12)=12\)	\(\max(5,12+10)+5=27\)

答えは \(\max(12,27)=27\) で、先ほどの考察と一致します。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(1)\)（DP 配列を持たず、直前の 2 値だけを使い回す。入力を配列に保持する場合は \(O(N)\)）

実装のポイント

• オーバーフロー対策: \(A_i\) の絶対値が最大 \(10^9\)、\(C\) も最大 \(10^9\)、\(N\) が最大 \(10^6\) なので、スコアは最大でおよそ \(2 \times 10^{15}\) 程度になります。32 bit 整数では溢れるので必ず 64 bit 整数（C++ なら long long）を使います。

• \(-\infty\) の扱い: \(dp1\) の初期値に LLONG_MIN をそのまま入れると \(+C\) や \(+A_i\) でオーバーフローします。LLONG_MIN / 4 のような十分小さいが余裕のある値を使う、あるいはコードのように「\(dp1\) が \(-\infty\) のときは \(+C\) の候補を作らない」と場合分けするのが安全です。別の方法として、\(dp[1][0]=0,\ dp[1][1]=A_1\) から始めて \(i=2\) 以降をループする実装にすれば \(-\infty\) を使わずに済みます。

• メモリと入力速度: \(N \le 10^6\) なので \(A\) を配列に持っても問題ありませんが、DP は \(A_i\) を 1 つずつ読みながら進められるため配列は不要です。\(10^6\) 個の整数入力は遅い入力方法だと時間がかかるので、C++ では scanf や高速読み込み（コードのように fread で一括読み込みして自前でパース）、Python なら sys.stdin の利用を推奨します。

• 答えが 0 になるケース: 「1 つもクリアしない」も許されるため、すべて負でボーナスも活かせない場合の答えは \(0\) です。\(dp[0][0]=0\) から始める実装なら自然にこれが含まれます。

  ソースコード

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

static char buf[1 << 25];

int main() {
    size_t len = fread(buf, 1, sizeof(buf) - 1, stdin);
    buf[len] = '\0';
    char *p = buf;
    auto readInt = [&]() -> long long {
        while (*p && (*p < '0' || *p > '9') && *p != '-') ++p;
        bool neg = false;
        if (*p == '-') { neg = true; ++p; }
        long long x = 0;
        while (*p >= '0' && *p <= '9') { x = x * 10 + (*p - '0'); ++p; }
        return neg ? -x : x;
    };

    long long n = readInt();
    long long C = readInt();

    const long long NEG = LLONG_MIN / 4;
    long long dp0 = 0, dp1 = NEG;
    for (long long i = 0; i < n; ++i) {
        long long a = readInt();
        long long n0 = max(dp0, dp1);
        long long cand = dp0;
        if (dp1 > NEG) cand = max(cand, dp1 + C);
        long long n1 = cand + a;
        dp0 = n0;
        dp1 = n1;
    }
    printf("%lld\n", max(dp0, dp1));
    return 0;
}

---

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