Day 086-Q4 — Convex Hull Trick（単調 CHT・二次コスト DP・$O(N)$）

問題

数直線上に $N$ 個の地点があり座標は狭義単調増加な整数列 $h_0 < h_1 < \dots < h_{N-1}$。地点 $0$ から地点 $N-1$ へ、$j$ から $i$（$j<i$）へのジャンプコスト $(h_i - h_j)^2 + C$ で移動する。総コストの最小値を求めよ。

入出力例

4 1
1 2 4 7

17

$dp[1]=2,\ dp[2]=7,\ dp[3]=\min(36,27,16)+1=17$。最適経路 $0\to1\to2\to3$。

概念図: 直線群の下側包絡線と単調クエリ

ヒント

add_line(-2*h[0], dp[0] + h[0]**2)
for i in range(1, N):
    dp[i] = query(h[i]) + h[i]**2 + C
    add_line(-2*h[i], dp[i] + h[i]**2)

模範解答

import sys

def solve():
    data = sys.stdin.buffer.read().split()
    N = int(data[0]); C = int(data[1])
    h = [int(data[2 + i]) for i in range(N)]

    M = []  # slopes
    B = []  # intercepts
    def bad(i1, i2, i3):
        # 直線 i2 が不要か: 交点(i1,i3)が(i1,i2)の左側
        return (B[i3] - B[i1]) * (M[i1] - M[i2]) <= (B[i2] - B[i1]) * (M[i1] - M[i3])
    def add_line(m, b):
        M.append(m); B.append(b)
        while len(M) >= 3 and bad(len(M) - 3, len(M) - 2, len(M) - 1):
            M.pop(-2); B.pop(-2)
    ptr = 0
    def query(x):
        nonlocal ptr
        if ptr >= len(M):
            ptr = len(M) - 1
        while ptr + 1 < len(M) and M[ptr + 1] * x + B[ptr + 1] <= M[ptr] * x + B[ptr]:
            ptr += 1
        return M[ptr] * x + B[ptr]

    dp = [0] * N
    add_line(-2 * h[0], dp[0] + h[0] * h[0])
    for i in range(1, N):
        dp[i] = query(h[i]) + h[i] * h[i] + C
        add_line(-2 * h[i], dp[i] + h[i] * h[i])
    print(dp[N - 1])

solve()

計算量: 各直線は高々 1 回追加・削除、クエリポインタも単調前進のため全体 $O(N)$。

Step-by-Step 解説

Step 1: DP 式の直線化

$(h_i-h_j)^2 = h_i^2 - 2h_jh_i + h_j^2$。$h_i$ 非依存の $dp[j]+h_j^2$ を切片、$-2h_j$ を傾きとする直線群の最小値問題へ。

Step 2: 単調性の確認

$h$ が狭義単調増加なので傾き $-2h_j$ は単調減少、$x=h_i$ は単調増加。両方単調 → 単調 CHT。

Step 3: 直線追加（下側包絡線）

新直線を末尾に追加し bad 判定で中間の不要直線を pop。凸性を保つ。

Step 4: クエリ（単調ポインタ）

次の直線が小さい間ポインタ前進。クエリ単調なので後戻り不要。

よくあるミス

次のステップ

• 発展問題: 傾き・クエリが非単調な場合の Li Chao Tree 版
• 発展問題: ちょうど $K$ 回ジャンプ制約（CHT + Aliens Trick / WQS 二分探索）

自己評価