Day 063-Q4 | 区間DP + 凸包トリック融合（O(N²→NlogN)）

問題

長さ $N$ の数列 $A_1, A_2, \ldots, A_N$ を ちょうど $K$ 個の連続区間に分割する。区間 $[l, r]$ のコストは $\text{cost}(l, r) = \left(\sum_{i=l}^{r} A_i\right)^2$ とする。総コストを最小化し、最小値を $\bmod 10^9+7$ で出力せよ。

制約

パラメータ	範囲
$N$	$1 \le N \le 5 \times 10^4$
$K$	$1 \le K \le N$
$A_i$	$1 \le A_i \le 10^9$

入出力例

入力例 1

6 3
1 3 2 4 1 2

出力例 1

最適分割例: [1],[3,2,4],[1,2] → $1 + 81 + 9 = 91$ ではなく、[1,3],[2,4],[1,2] → $16+36+9=61$... 実際の最適解を探索せよ。

概念図: CHT による DP 高速化

ヒント（段階的開示）

ヒント1: 方向性

素直な DP は $O(KN^2)$。Convex Hull Trick (CHT) で $O(KN)$ に落とせる。累積和 $S[i]$ を定義し、$\text{cost}(l,r) = (S[r]-S[l-1])^2$ と表す。DP 遷移を「傾き × クエリ点 + 切片」の形に変換することが鍵。

ヒント2: アプローチ

$dp[j-1][m] + S[m]^2 - 2S[m] \cdot S[i]$ を最小化。これは傾き $a_m = -2S[m]$、切片 $b_m = dp[j-1][m]+S[m]^2$、クエリ $x = S[i]$ の直線クエリ問題。$S[m]$ が単調なので傾きも単調 → 単調 deque で $O(N)$ per layer。

ヒント3: コード骨格

from collections import deque

for layer in range(K):
    lines = deque()  # (slope, intercept)

    def add(a, b):  # line: y = ax + b
        while len(lines) >= 2:
            s1,b1 = lines[-2]; s2,b2 = lines[-1]
            # (s2,b2) is unnecessary if intersection with (s1,b1) >= with (a,b)
            if (b-b1)*(s1-s2) <= (b2-b1)*(s1-a):
                lines.pop()
            else: break
        lines.append((a, b))

    def query(x):
        while len(lines) >= 2:
            s1,b1 = lines[0]; s2,b2 = lines[1]
            if s1*x+b1 >= s2*x+b2: lines.popleft()
            else: break
        return lines[0][0]*x + lines[0][1]

    for m in range(N):
        if prev[m] < INF:
            add(-2*S[m], prev[m]+S[m]*S[m])
    for i in range(1, N+1):
        curr[i] = query(S[i]) + S[i]*S[i]

模範解答 (Python)

import sys
from collections import deque
input = sys.stdin.readline
MOD = 10**9 + 7

def solve():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    S = [0] * (N + 1)
    for i in range(N):
        S[i + 1] = S[i] + A[i]

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

    for layer in range(K):
        curr = [INF] * (N + 1)
        lines = deque()  # (slope, intercept)

        def add_line(slope, intercept):
            while len(lines) >= 2:
                s1, b1 = lines[-2]
                s2, b2 = lines[-1]
                s3, b3 = slope, intercept
                if (b3 - b1) * (s1 - s2) <= (b2 - b1) * (s1 - s3):
                    lines.pop()
                else:
                    break
            lines.append((slope, intercept))

        for m in range(N):
            if prev[m] < INF:
                add_line(-2 * S[m], prev[m] + S[m] * S[m])

        for i in range(1, N + 1):
            if not lines:
                break
            x = S[i]
            while len(lines) >= 2:
                s1, b1 = lines[0]
                s2, b2 = lines[1]
                if s1 * x + b1 >= s2 * x + b2:
                    lines.popleft()
                else:
                    break
            s, b = lines[0]
            curr[i] = s * x + b + x * x

        prev = curr

    ans = prev[N]
    print(-1 if ans == INF else ans % MOD)

solve()

Step-by-Step 解説

Step 1: DP の定式化

$dp[j][i] = \min_{m<i} (dp[j-1][m] + (S[i]-S[m])^2)$。$j$ 層、$i$ 要素まで、最後の分割点が $m$。

Step 2: CHT への変換

$(S[i]-S[m])^2 = S[i]^2 - 2S[i]S[m] + S[m]^2$ と展開。$dp[j-1][m] + S[m]^2 - 2S[m] \cdot S[i]$ を最小化 → 傾き $a_m = -2S[m]$、切片 $b_m = dp[j-1][m]+S[m]^2$、クエリ $x = S[i]$ の CHT。

Step 3: 単調性の利用

$S[m]$ は非減少なので傾き $-2S[m]$ は非増加。$S[i]$ も非減少なのでクエリも単調。これにより deque を使った $O(N)$ per layer の CHT が適用できる。

Step 4: mod 処理

最終答えは非負整数なので % MOD で OK。中間計算はすべて整数演算で行い、float は使わない。

よくあるミス

ミス	原因	正しい書き方
`prev[0] = 0` を忘れる	初期状態が INF のまま	初期化で必須
bad 判定の不等号向き間違い	下凸包か上凸包かの混同	最小化では下凸包（$\le$ で pop）
deque を layer 間で再利用	前 layer のデータが混入	各 layer で `deque()` を初期化
$S[i]^2$ を切片に含める	クエリ点の定数部分の扱い	クエリ後に `+ S[i]*S[i]` を加算

次のステップ

発展問題: $K$ が $O(N)$ の場合に SMAWK アルゴリズムで $O(N\log N)$ を達成せよ（四辺形不等式 + 分割統治最適化の組み合わせ）。

自己評価

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