Day 126-Q2 | モノトニックキュー最適化DP

問題

$N$ 日間の求人があり、$i$ 日目（$1$-indexed）に働くと報酬 $A_i$ が得られる。ただし、一度働いた日から次に働ける日までは少なくとも $K$ 日空けなければならない（$i$日目に働いたら、次に働けるのは $i+K$ 日目以降）。

働く日を自由に選んで（0日でもよい）、得られる報酬の総和を最大化せよ。

入力形式

N K
A_1 A_2 ... A_N

制約

$1 \le N \le 500000$

$1 \le K \le N$

$1 \le A_i \le 10^9$

入出力例

入力例1

5 2
1 5 3 2 4

出力例1

2日目(5)と5日目(4)を選ぶと間隔3日≥K=2で合計9

入力例2

3 1
10 10 10

出力例2

K=1なので毎日働ける

概念図

ヒント（段階的開示）

ヒント1（方向性）

素朴なDP dp[i] = i日目まで見たときの最大報酬 を定義し、「$i$日目に働く／働かない」で遷移を作ると、働く場合は「$i-K$日以前のどこかで最後に働いた（または一度も働いていない）」状態からの遷移になる。この「過去のある区間内の最大値」を毎回線形探索すると $O(NK)$ になり間に合わない。

ヒント2（アプローチ）

$dp[i]$ を「$i$日目までを見て、$i$日目に働くかどうかを問わない最大報酬」と定義すると、遷移は $dp[i] = \max(dp[i-1],\ A_i + dp[i-K-1])$ となる。この「一定区間だけ後ろにずれた値を参照する」構造の一般形（ウィンドウ内最大値を毎回参照する版）を、単調キュー（モノトニックデック）で $O(N)$ に高速化する。

ヒント3（誘導）

デックには「(値, 添字)」を格納し、デックの先頭が常にウィンドウ内の最大値になるように保つ。

from collections import deque

dq = deque()
dp = [0] * (n + 1)
for i in range(1, n + 1):
    while dq and dq[0][1] < i - K:
        dq.popleft()
    best_prev = dq[0][0] if dq else 0
    work_today = A[i] + best_prev
    dp[i] = max(dp[i - 1], work_today)
    while dq and dq[-1][0] <= dp[i]:
        dq.pop()
    dq.append((dp[i], i))

模範解答 (Python)

import sys
from collections import deque


def solve():
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    k = int(data[1])
    a = [0] + [int(x) for x in data[2:2 + n]]

    dp = [0] * (n + 1)
    dq = deque()
    dq.append((0, 0))

    for i in range(1, n + 1):
        while dq and dq[0][1] > i - k:
            dq.popleft()
        best_prev = dq[0][0] if dq else float('-inf')
        work_today = a[i] + best_prev if best_prev != float('-inf') else float('-inf')
        dp[i] = max(dp[i - 1], work_today)

        while dq and dq[-1][0] <= dp[i]:
            dq.pop()
        dq.append((dp[i], i))

    print(dp[n])


solve()

Step-by-Step 解説

1DP状態設計
dp[i] を「$1$〜$i$日目までを見て得られる最大報酬」と定義する。これにより遷移が単純なmaxの形になり、答えは dp[N]。

2遷移の分解
「働かない」場合は dp[i-1] を引き継ぐ。「働く」場合は直近で働いたのが $i-K$日目以前という条件下での max(dp[j] for j<=i-K) + A[i]。

3単調デックによる高速化
「区間内 dp[j] の最大値」を毎回線形探索すると間に合わないため、単調減少デックの先頭が常にウィンドウ内最大値を保つよう管理する。

4計算量
各添字はデックに高々1回push・1回popされるため、全体で $O(N)$ の償却計算量となる。

5実装上の注意
dp[0]=0（何も働かない）を初期状態としてデックに含めておくことで、$i\le K$ の日でも正しく扱える。

よくあるミス

ミス	原因	正しい書き方
ウィンドウ条件の不等号の向きを誤る	「$i-K$日目以前」の境界をoff-by-oneで誤る	有効添字の条件を式で確認してから実装する（本問題は $j\le i-K$）
`dp[0]` を初期状態としてデックに入れ忘れる	「一度も働かない」ケースの見落とし	初期化時に `dq.append((0,0))` を必ず行う
デックに単調性を維持せず全要素を残す	「不要な要素を消す」操作を省略	追加時に自分以下の末尾要素を必ずpopしてから追加する
単調デックが不要な単純1点参照ケースと混同	本問題は実は `dp[i-K-1]` だけで足りる特殊形	一般化された可変ウィンドウ最大値問題との違いを意識する

次のステップ

発展: 報酬に加えて「同じ日に複数の仕事から1つ選ぶ」など多次元化した場合の単調デックDP拡張
次回予告: 有向グラフの全域木数え上げ（Directed Matrix-Tree定理・行列式によるarborescence数え上げ）

自己評価

完全理解おおむね理解要復習

Day 126-Q2 — モノトニックキュー最適化DP

問題