概要

\(N\) 日間の各日について工場を「稼働」させるか「休止」させるかを選択し、得られる利益の合計を最大化する問題です。前日の状態によって得られる利益や選択できる行動（2日連続休止の禁止）が制限されるため、動的計画法（DP）を用いて効率的に解くことができます。

考察

1. 素朴なアプローチ（全探索）とその限界

各日について「稼働」か「休止」かの \(2\) 通りの選択肢があるため、考えられる稼働計画は最大で \(2^N\) 通り存在します。本問題の制約は \(N \le 10^6\) であるため、すべての場合を試す全探索では制限時間（TLE）に到底間に合いません。

2. 問題の構造への着目

\(i\) 日目の行動と利益を決定する際に必要な情報は、過去すべての履歴ではなく「直前の日（\(i-1\) 日目）に工場が稼働していたか休止していたか」だけです。 具体的には、以下のルールがあります： - \(i-1\) 日目が休止だった場合： - \(i\) 日目は必ず稼働させなければならない（2日連続休止が禁止されているため）。 - このとき得られる利益は \(A_i\)。 - \(i-1\) 日目が稼働していた場合： - \(i\) 日目を休止させることができる（得られる利益は \(0\)）。 - \(i\) 日目を稼働させることもできる（得られる利益は \(A_i - C\)）。

このように、「前日の状態」さえ覚えておけばその日の最適な選択を決定できるため、動的計画法（DP）を適用できます。

アルゴリズム

各日について、その日を「休止」したか「稼働」させたかの \(2\) つの状態を管理します。

DPテーブル（状態）の定義

\(i\) 日目 (\(1 \le i \le N\)) まで決定した時点での最大利益を以下のように定義します： - \(dp[i][0]\): \(i\) 日目を休止させたときの最大利益 - \(dp[i][1]\): \(i\) 日目を稼働させたときの最大利益

初期値（1日目）

• 1日目を休止させる場合：利益は \(0\) なので、\(dp[1][0] = 0\)
• 1日目を稼働させる場合：前日は存在しないためメンテナンス費用はかからず利益は \(A_1\) なので、\(dp[1][1] = A_1\)

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

• \(i\) 日目を休止させる場合 (\(dp[i][0]\))： 2日連続で休止することはできないため、前日は稼働している必要があります。 $\(dp[i][0] = dp[i-1][1]\)$
• \(i\) 日目を稼働させる場合 (\(dp[i][1]\))： 前日が休止だった場合と、前日も稼働していた場合のうち、より利益が大きくなる方を選択します。
  • 前日が休止だった場合：前日までの利益に \(+ A_i\)
  • 前日も稼働していた場合：前日までの利益に \(+ A_i - C\) $\(dp[i][1] = \max(dp[i-1][0] + A_i, \; dp[i-1][1] + A_i - C)\)$

答えの計算

\(N\) 日目まで計算した後、最終日を休止した場合と稼働させた場合の最大値が答えとなります。 $\(\text{答え} = \max(dp[N][0], \; dp[N][1])\)$

なお、\(i\) 日目の計算には \(i-1\) 日目の値しか使わないため、\(N\) 日分のテーブルをすべて保持する必要はなく、直前の状態を表す変数 \(2\) つだけを更新していくことで省メモリに実装できます。

計算量

• 時間計算量: \(O(N)\) 各日について定数回（数回）の足し算・比較を行うだけなので、\(N = 10^6\) でも数ミリ秒〜数十ミリ秒程度で高速に動作します。
• 空間計算量: \(O(N)\) 数列 \(A\) を格納するために \(O(N)\) のメモリを使用します（DPの更新自体は直前の値のみを持つことで \(O(1)\) です）。

実装のポイント

• オーバーフローへの注意: \(N \le 10^6\) かつ \(A_i, C \le 10^9\) であるため、利益の合計は最大で約 \(10^6 \times 10^9 = 10^{15}\) に達します。また、損失が重なった場合は負の方向に絶対値が大きくなります。これらは通常の 32 ビット整数型（int）の範囲（約 \(\pm 2 \times 10^9\)）を大きく超えるため、DPの値や答えを格納する変数には必ず 64 ビット整数型（C++ の long long など）を使用してください。

• \(N = 1\) のコーナーケース: \(N = 1\) の場合、ループは一度も実行されず \(\max(0, A_1)\) が出力されます。\(A_1 < 0\) であれば休止（利益 \(0\)）を選び、\(A_1 \ge 0\) であれば稼働（利益 \(A_1\)）を選ぶため、問題の条件を正しく満たします。

  ソースコード

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    long long C;
    if (!(cin >> N >> C)) return 0;

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

    long long dp0 = 0;      // 前日休止
    long long dp1 = A[0];   // 前日稼働

    for (int i = 1; i < N; ++i) {
        long long next_dp0 = dp1;
        long long next_dp1 = max(dp0 + A[i], dp1 + A[i] - C);
        dp0 = next_dp0;
        dp1 = next_dp1;
    }

    cout << max(dp0, dp1) << "\n";

    return 0;
}

---

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