概要

仕事をいくつか選んで報酬の合計を最大化したいが、連番の仕事を両方選ぶたびに \(K\) 円のペナルティがかかる。これを最大利益になるように選ぶ問題です。

考察

重要なのは、ペナルティが「隣り合う番号同士（\(i\) と \(i+1\)）」の関係にしか依存しない点です。
つまり、仕事 \(i\) を選ぶかどうかの影響は、基本的に直前の仕事 \(i-1\) を選んだかどうかだけで決まります（それより前の選び方は、直前の状態に要約できる）。

素朴に「全ての部分集合を試す」やり方だと \(2^N\) 通りあり、\(N \le 2 \times 10^5\) では到底間に合いません。
そこで、「今見ている位置まででの最適値」を動的計画法（DP）で更新していきます。

ペナルティの発生条件を整理すると：

• 仕事 \(i\) を選び、かつ仕事 \(i-1\) も選んでいるときに限り、追加で \(K\) 引かれる
• それ以外（どちらか片方でも選ばない）なら、ペナルティは発生しない

この「直前も選んだか？」だけ覚えておけば十分、というのがDPの肝です。

アルゴリズム

\(dp0, dp1\) の2状態でDPします（添字 \(i\) は「現在位置」だと思ってください）。

• \(dp0\)：ここまで見てきた仕事の中で、最後の仕事（直近の仕事）を選んでいないときの最大利益
• \(dp1\)：ここまで見てきた仕事の中で、最後の仕事（直近の仕事）を選んでいるときの最大利益

仕事 \(i\)（報酬 \(A_i\)）を処理するときの遷移は以下です。

1) 新しい \(dp0\)（仕事 \(i\) を選ばない）

仕事 \(i\) を選ばないなら、直前が選ばれていたかどうかは関係なく、最大を取ればよい： - \(new0 = \max(dp0, dp1)\)

2) 新しい \(dp1\)（仕事 \(i\) を選ぶ）

仕事 \(i\) を選ぶ場合、直前の状態で場合分けします。

• 直前を選んでいない（\(dp0\)）から選ぶ：ペナルティなし
  利益は \(dp0 + A_i\)
• 直前も選んでいる（\(dp1\)）から続けて選ぶ：隣接ペアが1つ増えるのでペナルティ \(K\)
  利益は \(dp1 + A_i - K\)

したがって、 - \(new1 = \max(dp0 + A_i,\; dp1 + A_i - K)\)

これを \(i=1\) から順に更新していき、最後に \(\max(dp0, dp1)\) が答えです。

小さな例

\(A=[5,4,3],\; K=2\) のとき：

• 1番（5）を選ぶ：利益 5
• 2番（4）も選ぶと隣接なので \(-2\)：利益 \(5+4-2=7\)
• 3番（3）も選ぶとさらに隣接なので \(-2\)：利益 \(7+3-2=8\)

DPはこのように「連続で選んだら \(K\) 引く」を逐次的に処理できます。

計算量

• 時間計算量: \(O(N)\)（各仕事につき定数回の更新）
• 空間計算量: \(O(1)\)（\(dp0, dp1\) の2つだけ）

実装のポイント

• DP配列を持たず、\(dp0, dp1\) のみを更新することでメモリを節約できます。

• 初期化は

  • \(dp0=0\)（まだ何も選んでいない）
  • \(dp1=A_1\)（1番目を選ぶ） としています。

• 問題では「1つ以上選ぶ」必要がありますが、今回は \(A_i \ge 1\) なので最終的に \(\max(dp0,dp1)\) は必ず正となり、空集合（0）が最適になることはありません（そのため特別な処理なしで通ります）。

  ソースコード

import sys

def main():
    it = iter(map(int, sys.stdin.buffer.read().split()))
    N = next(it)
    K = next(it)
    A = [next(it) for _ in range(N)]

    dp0 = 0          # i not selected
    dp1 = A[0]       # i selected

    for i in range(1, N):
        ai = A[i]
        new0 = dp0 if dp0 > dp1 else dp1
        new1 = dp0 + ai
        cand = dp1 + ai - K
        if cand > new1:
            new1 = cand
        dp0, dp1 = new0, new1

    ans = dp0 if dp0 > dp1 else dp1
    print(ans)

if __name__ == "__main__":
    main()

---

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