D - 工場の稼働計画 / Factory Operation Plan 解説 by admin
Claude Opus 5 (High)概要
\(N\) 日間の各日について「稼働」「休止」を選び、連続稼働時にはコスト \(C\) が引かれ、\(2\) 日連続の休止は禁止という条件下で利益の総和を最大化する問題です。各日の状態が前日の状態のみに依存するので、典型的な区間 DP（状態を持つ DP）で \(O(N)\) で解けます。
考察
重要な観察
まず、ある日の利益がどう決まるかを整理します。
- \(i\) 日目に休止 → 利益 \(0\)
- \(i\) 日目に稼働、かつ \(i-1\) 日目は休止（または \(i=1\)）→ 利益 \(A_i\)
- \(i\) 日目に稼働、かつ \(i-1\) 日目も稼働 → 利益 \(A_i - C\)
つまり、\(i\) 日目の利益は「\(i\) 日目の選択」と「\(i-1\) 日目の選択」だけで決まります。「連続何日目か」は関係ありません（連続 3 日目でも 2 日目でも引かれるのは \(C\) だけ）。
また、禁止条件「\(2\) 日以上連続で休止できない」も、\(i-1\) 日目と \(i\) 日目の選択だけで判定できます。
したがって、「\(i\) 日目までの選択を決めたときの最大利益」は、\(i\) 日目の選択（稼働 / 休止）ごとに覚えておけば十分です。\(i+1\) 日目を決めるのに必要な過去の情報は「\(i\) 日目に稼働したか否か」だけだからです。
素朴なアプローチの問題
すべての選び方を全探索すると \(2^N\) 通りあり、\(N \le 10^6\) では到底間に合いません。
また、貪欲法（例えば「\(A_i > 0\) なら稼働、そうでなければ休止」）は誤答します。例として \(N = 3, C = 100, A = (10, -5, 10)\) を考えます。\(A_2 < 0\) なので \(2\) 日目を休止したいところですが、そうすると \(1,3\) 日目は稼働、\(2\) 日目は休止で利益 \(10 + 0 + 10 = 20\) となり、これが最適です。一方 \(C\) が小さい場合、例えば \(C = 1\) で \(A = (10, -5, 10)\) なら、全日稼働して \(10 + (-5-1) + (10-1) = 13\) より、やはり \(2\) 日目休止の \(20\) が良いです。逆に \(A = (10, 8, 10)\), \(C = 100\) なら「\(A_i>0\) だから全部稼働」は \(10 + (8-100) + (10-100) = -172\) ですが、\(1\) 日目稼働・\(2\) 日目休止・\(3\) 日目稼働で \(20\) が最適です。このように「稼働するか」の判断は隣接の選択と絡み合うため、局所的な判断だけでは決められません。
さらに、\(A_i\) が負でも「\(2\) 日連続休止禁止」のせいでやむを得ず損をする日を稼働させる必要がある場合もあります（例：\(N=3\), \(A=(-5,-5,-5)\) なら \(2\) 日目だけ稼働などで最善を選ぶ）。この制約を正しく扱うためにも DP が適しています。
解決方法
状態を「その日を稼働したか休止したか」の \(2\) 通りに絞った DP を行います。状態数 \(2N\)、遷移も定数個なので \(O(N)\) で解けます。
アルゴリズム
以下の DP を定義します。
- \(\mathrm{dp}[i][0]\) : \(i\) 日目を休止させたときの、\(1 \sim i\) 日目までの利益の最大値
- \(\mathrm{dp}[i][1]\) : \(i\) 日目を稼働させたときの、\(1 \sim i\) 日目までの利益の最大値
初期値（\(i = 1\)）
\[\mathrm{dp}[1][0] = 0,\quad \mathrm{dp}[1][1] = A_1\]
初日は前日がないので、稼働しても \(C\) は引かれません。
遷移（\(i \ge 2\)）
\(i\) 日目を休止する場合、\(2\) 日連続休止は禁止なので前日は必ず稼働です：
\[\mathrm{dp}[i][0] = \mathrm{dp}[i-1][1]\]
\(i\) 日目を稼働する場合、前日は休止でも稼働でもよく、前日が稼働なら \(C\) が引かれます：
\[\mathrm{dp}[i][1] = \max\bigl(\mathrm{dp}[i-1][0] + A_i,\ \ \mathrm{dp}[i-1][1] + A_i - C\bigr)\]
答え
\[\max\bigl(\mathrm{dp}[N][0],\ \mathrm{dp}[N][1]\bigr)\]
期間外の状態は考えないので、最終日は稼働・休止どちらでも構いません。
具体例
\(N = 4\), \(C = 3\), \(A = (5, 4, -2, 6)\) の場合：
| \(i\) | \(A_i\) | \(\mathrm{dp}[i][0]\)（休止） | \(\mathrm{dp}[i][1]\)（稼働） |
|---|---|---|---|
| 1 | 5 | \(0\) | \(5\) |
| 2 | 4 | \(5\) | \(\max(0+4,\ 5+4-3) = 6\) |
| 3 | -2 | \(6\) | \(\max(5-2,\ 6-2-3) = 3\) |
| 4 | 6 | \(3\) | \(\max(6+6,\ 3+6-3) = 12\) |
答えは \(\max(3, 12) = 12\)。実際「稼働・稼働・休止・稼働」で \(5 + (4-3) + 0 + 6 = 12\) です。
なお \(\mathrm{dp}[i][0]\) は「前日が稼働」しか許されないため、\(i \ge 2\) では常に定義できます（\(\mathrm{dp}[i-1][1]\) は必ず有効な値を持つ）。よって実際には「到達不可能状態」は生じませんが、実装上は念のため \(-\infty\) を扱えるようにしておくと安全です。
計算量
- 時間計算量: \(O(N)\)
- 空間計算量: \(O(1)\)（入力を読みながら処理する場合。配列に \(A\) を保持しても \(O(N)\)）
実装のポイント
オーバーフローに注意：\(|A_i| \le 10^9\)、\(N \le 10^6\) なので利益の絶対値は最大 \(10^9 \times 10^6 = 10^{15}\) 程度、さらに \(C\) の累積も加わり \(2 \times 10^{15}\) 程度になります。
int（約 \(2 \times 10^9\)）では溢れるので 64 bit 整数（long long） を使います。配列は不要：\(\mathrm{dp}[i]\) は \(\mathrm{dp}[i-1]\) のみに依存するので、変数
dp0,dp1を使い回して \(O(1)\) 空間にできます。更新時は「新しい値を一時変数に計算してから代入する」ことに注意（dp1を先に上書きするとdp0の計算が壊れます）。入力の高速化：\(N\) が最大 \(10^6\) なので、C++ では
cinにios::sync_with_stdio(false); cin.tie(nullptr);を付けるか、上のコードのようにfreadによる自前パースを使うと安全です。負の数（-）の読み取りも忘れずに実装します。\(N = 1\) のケース：ループに入らず \(\max(0, A_1)\) が答えになります（\(A_1\) が負なら休止して \(0\)）。上の実装は初期値だけで正しく処理されます。
\(C = 0\) や \(C\) が非常に大きい場合も同じ式で自然に処理できるので、場合分けは不要です。
ソースコード
#include <bits/stdc++.h>
using namespace std;
static char buf[1 << 25];
int main() {
size_t len = fread(buf, 1, sizeof(buf) - 1, stdin);
buf[len] = '\0';
char *p = buf;
auto readInt = [&]() -> long long {
while (*p && (*p < '0' || *p > '9') && *p != '-') ++p;
bool neg = false;
if (*p == '-') { neg = true; ++p; }
long long v = 0;
while (*p >= '0' && *p <= '9') { v = v * 10 + (*p - '0'); ++p; }
return neg ? -v : v;
};
long long N = readInt();
long long C = readInt();
const long long NEG = LLONG_MIN / 4;
long long dp0, dp1; // 0: rest today, 1: work today
long long a1 = readInt();
dp0 = 0;
dp1 = a1;
for (long long i = 2; i <= N; ++i) {
long long a = readInt();
long long n0 = (dp1 == NEG ? NEG : dp1);
long long cand1 = (dp0 == NEG ? NEG : dp0 + a);
long long cand2 = (dp1 == NEG ? NEG : dp1 + a - C);
long long n1 = max(cand1, cand2);
dp0 = n0;
dp1 = n1;
}
long long ans = max(dp0, dp1);
printf("%lld\n", ans);
return 0;
}
この解説は claude5opus-high によって生成されました。