概要

各日において工場を「稼働」か「休止」にするかを選び、連続稼働時のメンテナンス費用 \(C\) や「2日連続休止不可」という制約のもとで、得られる総利益の最大値を求める問題です。

考察

1. 状態の依存関係に注目する

各日 \(i\) に得られる利益や選択できる行動は、「前日（\(i - 1\) 日目）に工場を稼働させていたか、休止させていたか」 にのみ依存しています。 - \(i\) 日目に休止する場合: - \(2\) 日連続で休止することはできないため、前日は必ず稼働していなければなりません。 - 得られる利益は \(0\) です。 - \(i\) 日目に稼働する場合: - 前日は休止・稼働のどちらでも構いません。 - 前日が休止だった場合、利益は \(+A_i\) です。 - 前日も稼働していた場合、メンテナンス費用がかかるため利益は \(+ (A_i - C)\) です。

2. 素朴なアプローチとその限界

各日について「稼働」「休止」の \(2\) 通りを試す全探索を考えると、全体の組み合わせは \(2^N\) 通りになります。 本問題では \(N \le 10^6\) であるため、到底実行時間制限に間に合いません。

3. 動的計画法（DP）による解決

未来の決定に必要な情報は「前日に稼働していたかどうか」と「そこまでの利益の最大値」だけです。したがって、日ごとに状態をまとめて記録していく動的計画法（DP）が有効です。

アルゴリズム

以下の \(2\) つの状態を定義して DP を行います。

• \(dp_0\): 直前の日を「休止」としたときの、これまでの利益の最大値
• \(dp_1\): 直前の日を「稼働」としたときの、これまでの利益の最大値

初期状態（1日目）

• \(1\) 日目を休止する場合: 利益は \(0\) なので、\(dp_0 = 0\)
• \(1\) 日目を稼働する場合: 利益は \(A_1\) なので、\(dp_1 = A_1\)

状態遷移（\(i = 2, 3, \dots, N\) 日目）

\(i\) 日目の状態を、前日までの値から更新します。

1. \(i\) 日目に休止する場合 (\(new\_dp_0\)): 前日は稼働している必要があるため、前日の \(dp_1\) の値がそのまま引き継がれます。 $\(new\_dp_0 = dp_1\)$

2. \(i\) 日目に稼働する場合 (\(new\_dp_1\)):

   • 前日が休止だった場合: 得られる利益の合計は \(dp_0 + A_i\)
   • 前日も稼働していた場合: 得られる利益の合計は \(dp_1 - C + A_i\)

この \(2\) つのうち大きい方を選択します。 $\(new\_dp_1 = A_i + \max(dp_0, dp_1 - C)\)$

最終的な答え

\(N\) 日目まで更新を終えたあと、最終日の状態は休止・稼働のどちらでも良いため、\(\max(dp_0, dp_1)\) が答えとなります。

計算量

• 時間計算量: \(O(N)\) \(1\) 日目から \(N\) 日目までを \(1\) 回ずつ順番に計算します。各日の遷移は定数時間 \(O(1)\) なので、全体で \(O(N)\) となり、\(N = 10^6\) でも制限時間内に十分余裕を持って間に合います。
• 空間計算量: \(O(N)\) 入力の配列 \(A\) を保持するメモリとして \(O(N)\) かかります。DPのテーブル自体は前日の値のみを保持するため \(O(1)\) の追加メモリで動作します。

実装のポイント

• 高速な入出力: Python では \(N\) が \(10^6\) 規模になると入力の受け取りに時間がかかるため、sys.stdin.read().split() を用いて一度にデータを読み込むことで実行時間を大幅に短縮できます。

• 変数の使い回し: サイズ \(N\) の DP 配列を用意することなく、前日の結果を表す \(2\) つの変数（dp0, dp1）を更新していくことで、余分なメモリ消費を防ぎ、キャッシュ効率も高めています。

  ソースコード

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 = A[0]
    
    for a in A[1:]:
        new_dp0 = dp1
        val = dp1 - C
        new_dp1 = a + (dp0 if dp0 > val else val)
        dp0 = new_dp0
        dp1 = new_dp1
        
    print(dp0 if dp0 > dp1 else dp1)

if __name__ == '__main__':
    main()

---

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