Day 039-Q4 | Monge 行列 + 分割統治最適化 DP

問題

$N$ 個の都市（座標 $x_i$、ソート済み）を $K$ グループ（連続する集合）に分割して、各グループの最左端と最右端の距離の 2 乗のコスト和を最小化する。

$$\text{minimize} \quad \sum_{j=0}^{K-1} (x_{g_{j+1}-1} - x_{g_j})^2$$

制約

$2 \le K \le N \le 10^5$

$0 \le x_1 < x_2 < \cdots < x_N \le 10^9$

時間制限: 3sec / メモリ: 256MB

答えは 64bit 整数に収まる

入出力例

入力例 1

6 2
1 3 6 10 15 21

出力例 1

最適: [1,3,6,10] と [15,21] → $(10-1)^2 + (21-15)^2 = 81 + 36 = 117$。

概念図: 分割統治最適化 DP

ヒント（段階的開示）

ヒント1: DP の定式化

$dp[k][i]$ = 都市 $1..i$ を $k$ グループに分割した最小コスト。
$dp[k][i] = \min_{k-1 \le j < i}(dp[k-1][j] + C(j+1, i))$
$C(l, r) = (x_r - x_l)^2$（グループ $[l..r]$ のコスト）

ヒント2: 最適分割点の単調性

コスト $C(j+1, i) = (x_i - x_{j+1})^2$ は $j$ について「四辺形不等式」を満たす（凸型コスト）。これにより最適分割点 $opt(i)$ は $i$ について単調増加する。

ヒント3: 分割統治の実装

def rec(il, ir, jl, jr):
    if il > ir: return
    im = (il + ir) // 2
    best_val, best_j = INF, jl
    for j in range(jl, min(jr, im - 1) + 1):
        v = dp_prev[j] + cost(j + 1, im)
        if v < best_val:
            best_val, best_j = v, j
    dp_cur[im] = best_val
    rec(il, im - 1, jl, best_j)    # 左半分: opt <= best_j
    rec(im + 1, ir, best_j, jr)    # 右半分: opt >= best_j

模範解答 (Python)

import sys
input = sys.stdin.readline

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

    INF = float('inf')

    def cost(l, r):  # 1-indexed [l,r]
        return (X[r-1] - X[l-1]) ** 2

    # k=1 の初期化
    dp = [INF] * (N + 1)
    dp[0] = 0
    for i in range(1, N + 1):
        dp[i] = cost(1, i)

    for k in range(2, K + 1):
        ndp = [INF] * (N + 1)

        def rec(il, ir, jl, jr):
            if il > ir:
                return
            im = (il + ir) // 2
            best_val = INF
            best_j = jl
            for j in range(jl, min(jr, im - 1) + 1):
                if dp[j] == INF:
                    continue
                v = dp[j] + cost(j + 1, im)
                if v < best_val:
                    best_val = v
                    best_j = j
            ndp[im] = best_val
            rec(il, im - 1, jl, best_j)
            rec(im + 1, ir, best_j, jr)

        rec(k, N, k - 1, N - 1)
        dp = ndp

    print(dp[N])

solve()

Step-by-Step 解説

1DP の定式化
$dp[k][i]$ = 都市 $1..i$ を $k$ グループに分割した最小コスト。遷移は最適分割点 $j$ を全探索。

2四辺形不等式の確認
$(x_c - x_a)^2 + (x_d - x_b)^2 \le (x_d - x_a)^2 + (x_c - x_b)^2$ の確認（$a \le b \le c \le d$）。成立すれば最適分割点が単調。

3分割統治最適化
中点 $im$ に対して最適 $j$ を探し、左右の区間の探索範囲を縮小する。各層 $O(N)$、$O(\log N)$ 層で $O(N \log N)$。

4K 層の反復
$k = 2$ から $K$ まで反復。前の層の dp を使って次の層を計算。

5再帰の境界
il > ir で終了、min(jr, im-1) で $j < im$（自己分割回避）を保証。

計算量

各層: $O(N \log N)$（分割統治最適化）
全体: $O(KN \log N)$
WQS 二分探索と組み合わせると: $O(N \log N \log C)$

よくあるミス

ミス	原因	正しい書き方
単調性を確認せずに適用	コストが四辺形不等式を満たさない	小さな例で検証してから実装
終了条件 il > ir を忘れる	無限再帰	`if il > ir: return` を先頭に
k グループの最小都市数を無視	j < k-1 での探索	`rec(k, N, k-1, N-1)` で初期化
j < im の制約漏れ	自己分割が発生	`min(jr, im-1)` で j < im を保証

次のステップ

発展: $K$ が大きい場合 → WQS 二分探索 (Aliens Trick) と組み合わせて $O(N \log N \log C)$
応用: SMAWK アルゴリズムで $O(N)$ の最適化

自己評価

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

Day 039-Q4 — Monge 行列 + 分割統治最適化 DP

問題

制約