概要

隣り合うステージを両方クリアするとボーナスが得られる条件のもとで、最終スコアを最大化します。「直前のステージをクリアしたかどうか」を状態に持つ動的計画法（DP）で解けます。

考察

各ステージについて「クリアする・しない」をすべて試すと、組み合わせは \(2^N\) 通りあります。これでは \(N \le 10^6\) に対して間に合いません。

また、単に \(A_i\) が正のステージだけをクリアする方法も正しくありません。負のステージでも、コンボボーナスによってクリアしたほうが得になる場合があります。

例えば、\(C=5\)、\(A=(3,-2,3)\) の場合を考えます。

• ステージ \(1,3\) だけをクリアすると、スコアは \(3+3=6\)
• すべてクリアすると、スコアは \(3-2+3+5 \times 2=14\)

このように、ステージ単独の得点だけでは判断できません。

ここで重要なのは、ステージ \(i\) をクリアしたときにコンボボーナスが付くかどうかは、ステージ \(i-1\) をクリアしたかどうかだけで決まることです。

したがって、それまでにクリアしたステージをすべて覚える必要はありません。「直前をクリアしていない場合」と「直前をクリアしている場合」それぞれの最大スコアを持てば十分です。

アルゴリズム

ステージ \(1\) から順に処理します。ステージ \(i\) まで処理した時点で、次の \(2\) つの値を管理します。

• dp0：ステージ \(i\) をクリアしない場合の、ステージ \(1\) から \(i\) までの最大スコア
• dp1：ステージ \(i\) をクリアする場合の、ステージ \(1\) から \(i\) までの最大スコア

初期値

まだステージを処理していない状態を、次のように表します。

• dp0 \(=0\)
• dp1 \(=-\infty\)

直前のステージをクリアした状態は存在しないため、dp1 を選ばれないほど小さな値にしておきます。コードでは \(-10^{30}\) を使っています。

遷移

次に処理するステージの得点を \(a\) とします。

1. このステージをクリアしない場合

直前をクリアしていても、していなくても構いません。得点もボーナスも追加されないので、

\(\mathrm{next0}=\max(\mathrm{dp0},\mathrm{dp1})\)

となります。

2. このステージをクリアする場合

直前のステージの状態で場合分けします。

• 直前をクリアしていない場合：dp0 に \(a\) を加える
• 直前をクリアしている場合：dp1 に \(a+C\) を加える

よって、

\(\mathrm{next1}=\max(\mathrm{dp0},\mathrm{dp1}+C)+a\)

となります。

この \(2\) つを新しい dp0, dp1 として、次のステージへ進みます。

答え

最後のステージはクリアしてもしなくてもよいので、答えは

\(\max(\mathrm{dp0},\mathrm{dp1})\)

です。

各遷移は「今回クリアするか」と「直前をクリアしたか」のすべての場合を網羅しています。また、同じ状態なら、それまでのスコアが大きい選び方ほど以後も有利です。そのため、各状態の最大値だけを残すことで最適解を求められます。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: DP の補助領域は \(O(1)\)。ただし、提示コードは入力を一括で読み込むため、入力保持を含めると \(O(N)\)

各ステージで定数回の比較と加算を行うだけです。

実装のポイント

• 更新前の値を使う順序に注意します。
  提示コードでは、まず next0 を計算し、その後 dp1 を更新し、最後に dp0 = next0 としています。先に dp0 を上書きすると、dp1 の遷移に必要な更新前の値が失われます。

• 不可能な状態は十分小さい値で表します。
  dp1 の初期値を \(0\) にすると、最初のステージにもコンボボーナスを付けてしまう可能性があります。\(-10^{30}\) は、この問題のスコアの範囲に対して十分小さい値です。

• スコアは 32 ビット整数に収まりません。
  最大スコアはおよそ \(2 \times 10^{15}\) に達します。Python ではそのまま扱えますが、他言語では 64 ビット整数が必要です。

• 何もクリアしない選択も自然に含まれます。
  dp0 を \(0\) で初期化し、毎回クリアしない選択を残すため、答えが負になることはありません。

  ソースコード

import sys


def main():
    data = map(int, sys.stdin.buffer.read().split())
    n = next(data)
    c = next(data)

    dp0 = 0
    dp1 = -10**30

    for a in data:
        next0 = dp0 if dp0 > dp1 else dp1
        combo = dp1 + c
        dp1 = (dp0 if dp0 > combo else combo) + a
        dp0 = next0

    print(dp0 if dp0 > dp1 else dp1)


if __name__ == "__main__":
    main()

---

この解説は gpt-6-astra-medium によって生成されました。