概要

各日の「稼働・休止」を選び、休止が連続しないようにしながら利益の合計を最大化します。前日の状態だけに注目した動的計画法（DP）で求められます。

考察

各日について稼働・休止のすべての組み合わせを調べると、候補は \(2^N\) 通りあります。\(N \le 10^6\) なので、この方法では間に合いません。

また、その日の利益だけを見て判断する貪欲法も使えません。今日の選択によって、翌日に休止できるかどうかや、メンテナンス費用が発生するかどうかが変わるためです。

例えば、\(C=0\)、\(A=(-1,-100)\) の場合、初日に目先の利益を優先して休止すると、翌日は必ず稼働することになり、合計利益は \(-100\) です。一方、初日に稼働して翌日に休止すれば、合計利益は \(-1\) になります。

ここで重要なのは、翌日の選択と利益に影響するのは、直前の日が稼働だったか休止だったかだけという点です。

• 前日が稼働なら、今日は稼働・休止のどちらも選べる。ただし、稼働すると費用 \(C\) がかかる。
• 前日が休止なら、今日は必ず稼働する。費用 \(C\) はかからない。

連続稼働日数は関係ないため、次の \(2\) 状態だけを管理すれば十分です。

アルゴリズム

1. DP の状態

\(i\) 日目までの条件を満たす計画について、次を定義します。

• \(\mathrm{active}_i\)：\(i\) 日目に稼働する場合の、合計利益の最大値
• \(\mathrm{resting}_i\)：\(i\) 日目に休止する場合の、合計利益の最大値

2. 初期値

初日は、計画期間外の状態を考慮しません。そのため、

• 稼働するなら、利益は \(A_1\)
• 休止するなら、利益は \(0\)

となり、初期値は次の通りです。

\(\mathrm{active}_1=A_1\)

\(\mathrm{resting}_1=0\)

3. 状態遷移

\(i \ge 2\) とします。

\(i\) 日目に稼働する場合

前日の状態によって、次の \(2\) 通りがあります。

• 前日も稼働：\(\mathrm{active}_{i-1}+A_i-C\)
• 前日は休止：\(\mathrm{resting}_{i-1}+A_i\)

大きい方を選ぶので、

\(\mathrm{active}_i=A_i+\max(\mathrm{active}_{i-1}-C,\ \mathrm{resting}_{i-1})\)

です。

\(i\) 日目に休止する場合

休止を連続させられないため、前日は必ず稼働している必要があります。今日の利益は \(0\) なので、

\(\mathrm{resting}_i=\mathrm{active}_{i-1}\)

です。

これらの遷移は、条件を満たすすべての前日の状態を網羅しています。同じ状態から先の選択肢は同じなので、その状態に至る最大利益だけを残せば、最適な計画を失うことはありません。

4. 答え

最終日は稼働・休止のどちらでもよいため、答えは

\(\max(\mathrm{active}_N,\ \mathrm{resting}_N)\)

です。

各日の計算には前日の値しか使わないので、配列は不要です。コードでは active と resting の \(2\) 変数を順に更新しています。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: DP の補助領域は \(O(1)\)。ただし、提示コードは入力を read().split() で一括読み込みするため、入力保持を含めると \(O(N)\) です。

実装のポイント

• 更新前の値を使う必要があります。
  コードでは、まず new_active を計算し、その後で resting = active、active = new_active の順に更新しています。先に active を上書きすると、休止状態の計算に当日の値を使ってしまいます。

• 途中の利益が負でも、その状態を残します。
  休止を連続させられないため、損失を出してでも稼働する必要がある場合があります。DP の値を勝手に \(0\) 以上へ補正してはいけません。

• \(N=1\) も同じ処理で対応できます。
  更新ループは実行されず、\(\max(A_1,0)\) が出力されます。

• 合計利益は 32 ビット整数の範囲を超えることがあります。
  Python の整数では問題ありませんが、他言語では 64 ビット整数型を使う必要があります。

  ソースコード

import sys


def main():
    values = map(int, sys.stdin.buffer.read().split())
    n = next(values)
    c = next(values)

    active = next(values)
    resting = 0

    for a in values:
        continued = active - c
        new_active = a + (continued if continued > resting else resting)
        resting = active
        active = new_active

    print(active if active > resting else resting)


if __name__ == "__main__":
    main()

---

この解説は gpt-6-astra-medium によって生成されました。