Day 074-Q2 | Monotone Queue DP 最適化（区間最大値コスト最小分割）

問題

整数列 $A_1, A_2, \ldots, A_N$ が与えられる。この列をいくつかの連続部分列（区間）に分割するとき、各区間 $[l, r]$（0-indexed）のコストを

$$\text{cost}(l, r) = (r - l) \cdot \max(A_l, A_{l+1}, \ldots, A_r)$$

と定義する。列全体を分割したときの全コストの最小値を求めよ。ただし各区間の長さは 1 以上 $K$ 以下でなければならない。

制約

パラメータ	範囲	備考
$N$	$1 \le N \le 3 \times 10^5$	列の長さ
$K$	$1 \le K \le N$	1区間の最大長
$A_i$	$0 \le A_i \le 10^9$	各要素

入出力例

入力例1

6 3
3 1 4 1 5 9

出力例1

入力例2

5 5
10 1 1 1 10

出力例2

概念図: DP 遷移と Sparse Table

ヒント

ヒント1（方向性）

$\text{dp}[i]$ = 最初の $i$ 要素を分割したときの最小コスト。遷移は「直前の分割点 $j$（$\max(0, i-K) \le j < i$）」から来る。$\text{dp}[i] = \min_{j} \text{dp}[j] + (i-1-j) \cdot \max(A[j..i-1])$。Naive は $O(NK)$。

ヒント2（アプローチ）

Sparse Table で区間最大値を $O(1)$ クエリ可能にし、各 $i$ について $j$ をスキャンするが、最適化のキーは「最大値が固定されるグループ」に分けて単調キューで処理すること。

あるいは Cartesian Tree 分解により、最大値を持つインデックスを軸にした分割DP を $O(N \log N)$ で実現できる。

ヒント3（ほぼ答え）

# Sparse Table 構築
import math
LOG = max(1, int(math.log2(N)) + 1)
sp = [A[:]]
for k in range(1, LOG + 1):
    prev = sp[k-1]
    cur = [max(prev[i], prev[i + (1 << (k-1))])
           for i in range(N - (1 << k) + 1)]
    sp.append(cur)

def query_max(l, r):  # [l, r] inclusive
    if l > r: return 0
    k = int(math.log2(r - l + 1))
    return max(sp[k][l], sp[k][r - (1 << k) + 1])

模範解答

import sys
import math
input = sys.stdin.readline

def solve():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))

    INF = float('inf')
    dp = [INF] * (N + 1)
    dp[0] = 0

    # Sparse Table for range max
    LOG = max(1, int(math.log2(N)) + 1) if N > 0 else 1
    sp = [A[:]]
    for k in range(1, LOG + 1):
        prev = sp[k-1]
        cur = []
        for i in range(N - (1 << k) + 1):
            cur.append(max(prev[i], prev[i + (1 << (k-1))]))
        sp.append(cur)

    def query_max(l, r):
        if l > r:
            return 0
        length = r - l + 1
        k = int(math.log2(length))
        return max(sp[k][l], sp[k][r - (1 << k) + 1])

    # DP: dp[i] = min_{j in [max(0,i-K), i-1]} dp[j] + (i-1-j)*max(A[j:i])
    for i in range(1, N + 1):
        lo = max(0, i - K)
        best = INF
        for j in range(lo, i):
            mx = query_max(j, i - 1)
            cost = (i - 1 - j) * mx
            cand = dp[j] + cost
            if cand < best:
                best = cand
        dp[i] = best

    print(dp[N])

solve()

Step-by-Step 解説

Step 1: DP の定義

dp[i] = A[0..i-1] の最初 $i$ 要素を有効に分割したときの最小コスト。dp[0] = 0（空）。遷移: dp[i] = min over j の区間最大値コスト。

Step 2: Sparse Table で区間最大値を O(1) に

Sparse Table は事前に $\text{sp}[k][i] = \max(A[i..i+2^k-1])$ を計算しておく。クエリ時は $k = \lfloor \log_2(r-l+1) \rfloor$ として max(sp[k][l], sp[k][r-2^k+1]) で $O(1)$。

Step 3: 単調デクによる真の O(N) 最適化

上記は $O(NK)$ の内ループを持つが、「最大値が同じ区間」をグループ化して単調デクを使うと真に $O(N)$ amortized になる。各要素の「最大値としての支配区間」を単調スタックで特定し、その区間内では $\text{dp}[j] + \text{const} \times j$ の最小値を deque で管理する。

Step 4: Cartesian Tree 分解

$A$ の Cartesian Tree（各ノードが対応区間の最大値）を構築すると、分割問題がツリー上の DFS DP に帰着する。計算量は $O(N \log N)$。

よくあるミス

ミス	原因	正しい書き方
区間のコスト式を誤る	長さ vs 端点差の混乱	問題文の定義を精読（長さ−1 = r−l）
Sparse Table の境界外	`l > r` でクラッシュ	`if l > r: return 0` をガード
K=1 のとき cost=0	長さ1区間は $(1-1) \times \max = 0$	正しく 0 になる（確認するだけで良い）
dp の初期値 INF の扱い	INF + cost でオーバーフロー	Python では float('inf') を使えば安全

次のステップ

発展問題: K 制約なし + コストが $(r-l+1)^2$ → 四辺形不等式 + 分割統治 DP
類題: AtCoder 「石の分割コスト」系問題
真の O(N): Cartesian Tree 分解 + DFS DP の完全実装

自己評価

理解度:

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

自分の回答:

気づき・メモ: