概要

各ステージをクリアするかどうかを選び、ステージの得点と隣接するステージ間のコンボボーナスの合計を最大化します。「直前のステージをクリアしたかどうか」を状態とする動的計画法で解けます。

考察

各ステージには「クリアする」「クリアしない」の \(2\) 通りの選択があるため、すべての組み合わせを調べると \(2^N\) 通りになります。\(N \le 10^6\) では間に合いません。

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

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

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

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

ここで、ステージ \(i\) をクリアするとき、新しく発生する可能性があるボーナスは、ペア \((i-1,i)\) に対するものだけです。したがって、直前のステージをクリアしたかどうかが分かれば、それ以前の選択を細かく覚える必要はありません。

直前の状態が同じなら、今後の得点の増え方も同じなので、それまでのスコアが最大のものだけを残せます。

アルゴリズム

ステージを左から順に処理し、次の \(2\) つの値を管理します。

• skip：処理済みの最後のステージをクリアしない場合の最大スコア
• take：処理済みの最後のステージをクリアする場合の最大スコア

1. 初期化

まだステージを処理していないときは、次のようにします。

• skip \(=0\)
• take \(=-\infty\)

何もクリアしていない状態のスコアは \(0\) です。一方、「直前のステージをクリアした状態」は存在しないため、take を十分小さい値にします。

2. 各ステージでの更新

ステージ \(i\) の得点を \(A_i\) とします。

ステージ \(i\) をクリアしない場合

直前のステージをクリアしたかどうかに関係なく、得点もボーナスも増えません。したがって、

\(\mathrm{next\_skip}=\max(\mathrm{skip},\mathrm{take})\)

となります。

ステージ \(i\) をクリアする場合

直前のステージの選択によって、次の \(2\) 通りがあります。

• 直前をクリアしていない：skip に \(A_i\) を加える
• 直前をクリアしている：take に \(A_i+C\) を加える

よって、

\(\mathrm{next\_take}=\max(\mathrm{skip},\mathrm{take}+C)+A_i\)

となります。

この \(2\) つを計算した後、skip と take をそれぞれ更新します。

3. 答え

すべてのステージを処理した後、最後のステージをクリアする場合としない場合のうち、大きいほうを出力します。

\(\mathrm{answer}=\max(\mathrm{skip},\mathrm{take})\)

各更新では、現在のステージをクリアするかどうかと、直前をクリアしたかどうかの全パターンを考慮しています。そのため、各状態の最大スコアが正しく保たれ、最後に全体の最大値が得られます。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(1)\)

各ステージを一度ずつ処理します。入力を読みながら更新できるため、配列 \(A\) を保存する必要はありません。

実装のポイント

• スコアには 64 bit 整数を使います。
  スコアは最大で \(N\cdot 10^9+(N-1)\cdot 10^9\) 程度になり、32 bit 整数には収まりません。コードでは long long を使用しています。

• 不可能な状態には十分小さい値を使います。
  コードでは \(-\infty\) の代わりに -(1LL << 60) を使っています。制約内のスコアより十分小さく、得点やボーナスを加えてもオーバーフローしません。

• 更新前の値を使って、次の状態を両方計算します。
  skip を先に書き換えると、next_take の計算に誤って更新後の値を使ってしまいます。next_skip と next_take を計算してから代入しましょう。

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

  ソースコード

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    long long C;
    cin >> N >> C;

    long long skip = 0;
    long long take = -(1LL << 60);

    for (int i = 0; i < N; ++i) {
        long long A;
        cin >> A;

        long long next_skip = max(skip, take);
        long long next_take = max(skip, take + C) + A;

        skip = next_skip;
        take = next_take;
    }

    cout << max(skip, take) << '\n';
    return 0;
}

---

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