概要

\(N\) 日間の各日について「稼働」「休止」を選び、利益の合計を最大化する問題です。休止は 2 日以上連続できず、連続稼働 2 日目以降はコスト \(C\) がかかります。典型的な 区間 DP ではなく「直前の日の状態」を持つ DP（bit DP 的な状態 DP） で解けます。

考察

重要な気づき

ある日の利益は、その日の選択（稼働/休止）と 前日の選択 だけで決まります。

• \(i\) 日目に休止 → 利益 \(0\)。ただし前日も休止だったらそもそも禁止。
• \(i\) 日目に稼働 → 前日が休止（または \(i=1\)）なら \(A_i\)、前日も稼働なら \(A_i - C\)。

つまり「前日が稼働だったか休止だったか」という情報 1 ビットだけを覚えておけば、\(i\) 日目以降の意思決定に必要な情報はすべて揃います。過去の詳しい履歴（何日連続で動かしたか等）は不要です。ここがポイントで、問題文の「連続して稼働している日数にかかわらず \(C\)」という条件がこれを保証しています。

素朴なアプローチの問題点

全ての稼働/休止の組み合わせを試すと \(2^N\) 通りで、\(N \le 10^6\) ではまったく間に合いません。

また「\(A_i > 0\) の日は稼働、\(A_i \le 0\) の日は休止」といった貪欲は誤りです。例えば

N=3, C=0, A = [5, -1, 5]

の場合、\(2\) 日目を休止したいところですが、\(C=0\) なので \(2\) 日目も稼働して \(5 + (-1-0) + (5-0) = 9\) とするのが最適です（\(2\) 日目を休止すると \(5+0+5=10\) で、こちらの方が良い例もあり）、逆に

N=3, C=100, A = [5, 5, 5]

では毎日稼働すると \(5 + (5-100) + (5-100) = -185\) ですが、\(2\) 日目を休止して \(5 + 0 + 5 = 10\) が最適です。このように \(C\) と \(A_i\) のバランスで最適解が変わるため、局所的な判断では決められません。

解決策

「前日が稼働 / 休止」の 2 状態を持つ DP を行えば、各日 \(O(1)\) で遷移でき、全体 \(O(N)\) で解けます。

アルゴリズム

DP の定義：

• \(\mathrm{work}[i]\) … \(i\) 日目まで見て、\(i\) 日目に 稼働 させたときの利益合計の最大値
• \(\mathrm{rest}[i]\) … \(i\) 日目まで見て、\(i\) 日目に 休止 させたときの利益合計の最大値

初期値（\(i=1\)）： $\(\mathrm{work}[1] = A_1,\qquad \mathrm{rest}[1] = 0\)$

（\(1\) 日目に稼働する場合、前日が存在しないので \(C\) は引かれません。）

遷移（\(i \ge 2\)）：

• \(i\) 日目に休止する場合、前日は必ず稼働していなければならない（2 日連続休止は禁止）ので $\(\mathrm{rest}[i] = \mathrm{work}[i-1]\)$
• \(i\) 日目に稼働する場合、前日は稼働でも休止でもよく $\(\mathrm{work}[i] = \max\bigl(\mathrm{rest}[i-1] + A_i,\ \ \mathrm{work}[i-1] + A_i - C\bigr)\)$

答え： $\(\max(\mathrm{work}[N],\ \mathrm{rest}[N])\)$

期間外の状態は考慮しないので、最終日はどちらの状態でも構いません。

具体例で確認

\(N=3, C=100, A=[5,5,5]\) の場合：

\(i\)	\(\mathrm{work}\)	\(\mathrm{rest}\)
1	\(5\)	\(0\)
2	\(\max(0+5,\ 5+5-100) = 5\)	\(5\)
3	\(\max(5+5,\ 5+5-100) = 10\)	\(5\)

答えは \(\max(10,5)=10\) となり、「稼働・休止・稼働」が最適だと分かります。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(1)\)（入力配列を除く。DP は直前の 2 値のみ保持）

実装のポイント

• 配列を持たず変数 2 つで回す：\(\mathrm{work}[i]\) の計算に \(\mathrm{rest}[i-1]\) が必要なので、更新順に注意します。新しい値を一時変数 nrest, nwork に入れてから代入すると安全です（rest = work を先に実行してしまうと古い rest が壊れます）。

• \(N=1\) の扱い：ループが回らず、\(\max(A_1, 0)\) が答えになります。上のコードは初期値のまま \(\max(\mathrm{work},\mathrm{rest}) = \max(A_1,0)\) を出力するので、特別扱い不要です。

• オーバーフロー：\(|A_i| \le 10^9\)、\(N \le 10^6\) なので合計は最大 \(10^{15}\) 程度。C++ 等では long long を使います（Python は多倍長整数なので問題なし）。

• 入出力の高速化：\(N \le 10^6\) なので、Python では input() を繰り返し呼ぶのではなく sys.stdin.buffer.read().split() で一括読み込みします。さらに、リストを作らず必要な要素だけ int() 変換しながらループすると定数倍が軽くなります。

• 休止が「必ず利益 0」であることに注意：\(\mathrm{rest}[i] = \mathrm{work}[i-1] + 0\) で、\(A_i\) は加算しません。

  ソースコード

import sys

def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    c = int(data[1])
    NEG = float('-inf')
    a1 = int(data[2])
    rest = 0
    work = a1
    for i in range(1, n):
        ai = int(data[2 + i])
        nrest = work
        nwork = rest + ai
        w2 = work + ai - c
        if w2 > nwork:
            nwork = w2
        rest = nrest
        work = nwork
    ans = rest if rest > work else work
    sys.stdout.write(str(ans) + "\n")

main()

---

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