概要

\(N\) 個の各ステージについてクリアするかどうかを選択し、クリア報酬 \(A_i\) と連続クリアによるコンボボーナス \(C\) の合計スコアを最大化する問題です。直前のステージをクリアしたかどうかを状態として持つ動的計画法（DP）を用いることで、時間計算量 \(O(N)\) で解くことができます。

考察

素朴なアプローチとその課題

各ステージについて「クリアする」「クリアしない」の 2 通りの選択肢があるため、すべての組み合わせを試す全探索では \(2^N\) 通りの計算が必要になります。本問の制約は \(N \le 10^6\) であるため、全探索では実行時間制限に到底間に合いません（TLE）。

また、「\(A_i > 0\) のステージのみをクリアする」というような単純な貪欲法も誤りです。例えば、\(A_i\) が負であっても、隣接するステージと同時にクリアすることでボーナス \(C\) が得られ、全体としてプラスになる場合があります。

動的計画法への帰着

ステージ \(i\) をクリアした際にボーナス \(C\) が得られるかどうかは、「直前のステージ \(i - 1\) をクリアしたかどうか」にのみ依存します。それより前のステージ（\(i - 2\) 以前）の選択状況は、ステージ \(i\) の獲得スコアには一切影響しません。

このように、過去の全体の状態ではなく直前の状態のみが必要となる問題では、動的計画法（DP）が有効です。ステージを先頭から順に見ていき、「直前のステージをクリアしたか」という情報だけを状態として記録しながら最適解を求めていくことができます。

アルゴリズム

以下のように DP の状態を定義します。

• \(dp_0\) : 現在のステージをクリアしなかった場合のスコアの最大値
• \(dp_1\) : 現在のステージをクリアした場合のスコアの最大値

ステージ \(i\) のスコア \(A_i\) を順に処理していく際、次のステージの状態は以下のように更新されます。

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

   • 直前のステージ \(i - 1\) をクリアしていてもしていなくても構いません。ボーナスは発生しないため、直前までの最大値をそのまま引き継ぎます。 $\(ndp_0 = \max(dp_0, dp_1)\)$

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

   • 直前をクリアしていなかった場合: 直前のスコア \(dp_0\) に \(A_i\) が加算されます。
   • 直前をクリアしていた場合: 直前のスコア \(dp_1\) に \(A_i\) に加えてコンボボーナス \(C\) が加算されます。
   • これらのうち、大きい方を採用します。 $\(ndp_1 = \max(dp_0 + A_i, \; dp_1 + A_i + C)\)$

初期値と終了状態

• ゲーム開始前（ステージ \(0\) の時点）では：
  • まだ何もクリアしていないため、\(dp_0 = 0\)
  • 「直前をクリアした」状態はあり得ないため、\(dp_1 = -\infty\)（十分に小さい値）
• すべてのステージを走査した後の \(\max(dp_0, dp_1)\) が求める最終スコアの最大値となります。

計算量

• 時間計算量: \(O(N)\)
  • ステージ数 \(N\) 回のループを行い、各ループ内では定数回の足し算と比較のみを行うため、全体で \(O(N)\) となります。\(N = 10^6\) でも十分に制限時間（2秒）以内に間に合います。
• 空間計算量: \(O(N)\)
  • 入力配列の保持に \(O(N)\) のメモリを使用します。DP の状態更新自体は直前の 2 つの値のみを保持するため、DP テーブルの空間計算量は \(O(1)\) です。

実装のポイント

• 初期値 \(-\infty\) の設定: \(A_i\) の値は最小で \(-10^9\) であり、累積すると非常に小さな負の値になり得ます。そのため、あり得ない状態を表す初期値には \(-10^{18}\) など十分に絶対値が大きい負の数を設定し、誤って最適値として選ばれないようにします。

• 高速な入出力: Python では \(N = 10^6\) の入力を 1 行ずつ読み込むとオーバーヘッドが大きくなるため、sys.stdin.read().split() などを用いて一度に読み込むことで高速化しています。

  ソースコード

import sys

def main():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    N = int(input_data[0])
    C = int(input_data[1])
    A = [int(x) for x in input_data[2:]]
    
    dp0 = 0
    dp1 = -10**18
    
    for a in A:
        ndp0 = dp0 if dp0 > dp1 else dp1
        v1 = dp0 + a
        v2 = dp1 + a + C
        ndp1 = v1 if v1 > v2 else v2
        dp0, dp1 = ndp0, ndp1
        
    print(dp0 if dp0 > dp1 else dp1)

if __name__ == '__main__':
    main()

---

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