Day 092-Q5 — Convex Hull Trick（分割コスト最小化DP）

問題

数直線上の $N$ 点、座標は狭義単調増加 $x_1 < x_2 < \dots < x_N$。連続する何個かのグループに分割する。グループ $x_p, \dots, x_q$ のコストは $(x_q - x_p)^2 + K$。全体コストの総和を最小化せよ。

入出力例

4 5
1 2 10 11

12

$\{1,2\}$ と $\{10,11\}$: $(2-1)^2+5 + (11-10)^2+5 = 6+6 = 12$ が最小。

概念図

ヒント

dp[i] = query(x[i]) + x[i]**2 + K
add_line(-2*x[i+1], dp[i] + x[i+1]**2)
# 傾き単調減少 & クエリ単調増加 → 単調CHT で O(N)

模範解答

import sys

class CHT:
    """min クエリ・傾き単調減少・クエリ点単調増加の単調CHT"""
    def __init__(self):
        self.m = []
        self.c = []
        self.ptr = 0

    def _bad(self, i1, i2, i3):
        # 直線 i2 が不要か（i1,i3 の交点が i1,i2 の交点より左）
        return (self.c[i3] - self.c[i1]) * (self.m[i1] - self.m[i2]) <= \
               (self.c[i2] - self.c[i1]) * (self.m[i1] - self.m[i3])

    def add(self, m, c):
        self.m.append(m); self.c.append(c)
        while len(self.m) >= 3 and self._bad(len(self.m) - 3, len(self.m) - 2, len(self.m) - 1):
            self.m.pop(-2); self.c.pop(-2)

    def _f(self, i, x):
        return self.m[i] * x + self.c[i]

    def query(self, x):
        if self.ptr >= len(self.m):
            self.ptr = len(self.m) - 1
        while self.ptr + 1 < len(self.m) and self._f(self.ptr + 1, x) <= self._f(self.ptr, x):
            self.ptr += 1
        return self._f(self.ptr, x)

def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0]); K = int(data[1])
    x = [0] + [int(data[2 + i]) for i in range(n)]   # 1-indexed

    dp = [0] * (n + 1)
    cht = CHT()
    cht.add(-2 * x[1], dp[0] + x[1] * x[1])           # j = 0
    for i in range(1, n + 1):
        dp[i] = cht.query(x[i]) + x[i] * x[i] + K
        if i < n:
            cht.add(-2 * x[i + 1], dp[i] + x[i + 1] * x[i + 1])  # j = i
    print(dp[n])

main()

計算量 $O(N)$。傾き・クエリ点がともに単調なので pop も追加も償却 $O(1)$。

Step-by-Step 解説

Step 1: DP 定義

$dp[i]$ は先頭 $i$ 点の最小分割コスト、$dp[0]=0$。最後のグループを $[j+1, i]$ とすると遷移は $dp[j]+(x_i-x_{j+1})^2+K$。

Step 2: 二乗展開で直線化

$X=x_i$ を固定変数とみなすと、各 $j$ は傾き $-2x_{j+1}$・切片 $dp[j]+x_{j+1}^2$ の直線。$dp[i]$ は「直線群の $X=x_i$ での最小値 $+ x_i^2 + K$」。

Step 3: 単調CHT（下側凸包）

傾きが単調減少で追加されるので、追加時に不要になった中間直線を末尾から取り除き下側凸包を保つ（_bad 判定）。

Step 4: クエリ点単調でポインタ前進

$x_i$ が増加するので最適直線の添字も単調前進。ptr を進めるだけで最小直線が得られる（二分探索不要）。

よくあるミス

次のステップ

• 発展: 傾き・クエリが非単調なら Li Chao Tree（$O(N\log C)$）
• 発展: monotone/Monge 性があれば分割統治DP・Knuth 最適化も比較
• 次回予告: Master Level ローテーション継続

自己評価