概要

各ステージを「クリアする / しない」を自由に選び、選んだステージの \(A_i\) の総和に加えて「隣接する 2 つを両方選んだ回数 \(\times C\)」が得られるとき、最終スコアの最大値を求める問題です。典型的な「区間 DP ではない、隣接関係のある選択問題」＝ 1 次元の bit DP（状態 2 個の DP） で解けます。

考察

素朴なアプローチ

すべてのクリアするステージの組み合わせを試すと \(2^N\) 通りあり、\(N \le 10^6\) ではまったく間に合いません。

貪欲は通らない

「\(A_i > 0\) のステージだけクリアすればよい」と考えたくなりますが、これは誤りです。たとえば

• \(N = 3,\ C = 4,\ A = (10, -5, 10)\)

の場合、正の \(A_i\) だけ選ぶ（ステージ \(1, 3\)）とボーナスが付かず \(20\) ですが、すべてクリアすると \(10 - 5 + 10 + 2 \times 4 = 23\) となり、こちらの方が大きくなります。つまり「損なステージでも、両隣をつなげてボーナスを 2 回もらうために選ぶ」ことが得になり得ます。

逆に

• \(N = 3,\ C = 4,\ A = (-5, 10, -5)\)

では、すべてクリアすると \(8\)、ステージ \(2\) のみで \(10\) なので、つなげない方が良いこともあります。よって「その場の符号」だけでは判断できず、左からの情報を持ち回る必要があります。

重要な観察

スコアへの寄与を見ると、

• ステージ \(i\) 自身の \(A_i\)
• 直前のステージ \(i-1\) をクリアしたかによって発生する \(C\)

しかありません。つまり、ステージ \(i\) を処理するときに知っておく必要があるのは「直前のステージをクリアしたかどうか」という 1 ビットの情報だけです。ここから DP が立ちます。

アルゴリズム

\(dp[i][0]\)：ステージ \(1 \dots i\) まで決めて、ステージ \(i\) をクリアしていないときの最大スコア \(dp[i][1]\)：ステージ \(1 \dots i\) まで決めて、ステージ \(i\) をクリアしたときの最大スコア

初期状態は「ステージ \(0\)」という仮想のステージを置いて $\(dp[0][0] = 0,\qquad dp[0][1] = -\infty\)\( （ステージ \)0$ は存在しないのでクリアした状態は禁止）とします。

遷移は以下の通りです。

• ステージ \(i\) をクリアする場合
  • 直前をクリアしていない → ボーナスなし：\(dp[i-1][0] + A_i\)
  • 直前もクリアした → ボーナス \(C\) が付く：\(dp[i-1][1] + C + A_i\) $\(dp[i][1] = \max(dp[i-1][0],\ dp[i-1][1] + C) + A_i\)$
• ステージ \(i\) をクリアしない場合（ボーナスは発生しない） $\(dp[i][0] = \max(dp[i-1][0],\ dp[i-1][1])\)$

答えは \(\max(dp[N][0], dp[N][1])\) です。\(dp[0][0]=0\) から始めているので「1 つもクリアしない（スコア \(0\)）」も自然に候補に含まれます。

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

\(i\)	\(dp[i][0]\)	\(dp[i][1]\)
0	0	\(-\infty\)
1	0	\(0 + 10 = 10\)
2	\(\max(0,10)=10\)	\(\max(0,\ 10+4) - 5 = 9\)
3	\(\max(10,9)=10\)	\(\max(10,\ 9+4) + 10 = 23\)

答え \(\max(10, 23) = 23\) で正しく求まっています。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(1)\)（入力配列を保持する場合は \(O(N)\)）

\(dp[i][\cdot]\) は \(dp[i-1][\cdot]\) しか使わないので、変数 2 個（dp0, dp1）を上書きしていくだけで十分です。

実装のポイント

• 配列を持たず 2 変数で回す：\(N = 10^6\) なので、長さ \(N\) の DP テーブルを 2 本作ると Python ではメモリ・時間の両方で厳しくなります。dp0, dp1 を更新するだけにします。更新時は「新しい値を一時変数に入れてから代入」して、\(dp[i-1]\) の値を壊さないよう注意します。

• 入力の高速化：sys.stdin.buffer.read().split() で一括読み込みし、必要な要素だけ int() 変換します。input() を \(10^6\) 回呼ぶのは致命的に遅いです。上のコードでは data[2], data[3], \dots を順に int 化しながらループしています。

• max() を使わず条件式に：Python では組み込み関数呼び出しのオーバーヘッドが大きいため、a if a > b else b の形にすると高速化できます（\(10^6\) 回のループでは効きます）。

• オーバーフロー / 初期値：スコアは最大で約 \(10^6 \times 10^9 \times 2 = 2 \times 10^{15}\) 程度になるので C++ 等では long long が必須です。Python は多倍長なので問題ありません。ただし \(-\infty\) に float('-inf') を使うと途中で float が混ざるので、出力時に int() を通す（コードのように）か、はじめから -10**18 のような十分小さい整数を使うのが安全です。

• \(C = 0\) や \(N = 1\)（\(dp[1][1] = A_1\)、答えは \(\max(0, A_1)\)）といった端のケースも、この DP はそのまま正しく処理します。

  ソースコード

import sys

def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    c = int(data[1])
    NEG = float('-inf')
    dp0 = 0
    dp1 = NEG
    for i in range(2, n + 2):
        a = int(data[i])
        t = dp1 + c
        nd1 = (dp0 if dp0 > t else t) + a
        nd0 = dp0 if dp0 > dp1 else dp1
        dp0 = nd0
        dp1 = nd1
    ans = dp0 if dp0 > dp1 else dp1
    sys.stdout.write(str(int(ans)) + "\n")

main()

---

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