問題
$N$ 個の都市が直線上に並んでいる。都市 $i$ の座標は $x_i$（昇順）。 都市 $i$ から都市 $j$（$i < j$）への移動コストは $(x_j - x_i)^2 + C$。 都市 $1$ から都市 $N$ に到達する最小総コストを求めよ。
制約
$2 \le N \le 5 \times 10^5$
$0 \le C \le 10^{18}$
$0 \le x_i \le 10^9$（昇順）
時間制限: 2sec
入出力例
入力例 1
3 5
0 3 7出力例 1
21- $1 \to 3$: $(7-0)^2 + 5 = 54$
- $1 \to 2 \to 3$: $(3-0)^2 + 5 + (7-3)^2 + 5 = 9+5+16+5 = 35$
- 最小 = $35$… (サンプルの数値は自分で確認すること)
概念図: Convex Hull Trick (CHT)
各 $i$ に対して直線 $f_i(t) = -2x_i \cdot t + (dp[i] + x_i^2)$ を管理。クエリ点 $t = x_j$ での最小値を求める。
ヒント (段階的開示)
ヒント1: DP 式の展開
$$dp[j] = x_j^2 + C + \min_{i < j}\{dp[i] + x_i^2 - 2x_i x_j\}$$
→ 直線 $f_i(t) = -2x_i \cdot t + (dp[i] + x_i^2)$ の $t = x_j$ での最小値。
ヒント2: 単調性の確認
傾き $m_i = -2x_i$ は $x_i$ 増加で単調減少。クエリ点 $t = x_j$ は単調増加。
→ 単調 CHT（デック）が使える → $O(N)$。
ヒント3: bad 判定（不要な直線の除去）
直線 $(l_1, l_2, l_3)$ で $l_2$ が不要：
$l_1$ と $l_3$ の交点 $\le$ $l_1$ と $l_2$ の交点 のとき，$l_2$ は常に $l_1$ か $l_3$ より悪い。
$l_1$ と $l_3$ の交点 $\le$ $l_1$ と $l_2$ の交点 のとき，$l_2$ は常に $l_1$ か $l_3$ より悪い。
def bad(l1, l2, l3):
m1,b1 = l1; m2,b2 = l2; m3,b3 = l3
return (b3-b1)*(m1-m2) <= (b2-b1)*(m1-m3)模範解答 (Python)
import sys
from collections import deque
input = sys.stdin.readline
def solve():
N, C = map(int, input().split())
X = list(map(int, input().split()))
INF = float('inf')
dp = [INF] * N
dp[0] = 0
def bad(l1, l2, l3):
m1,b1 = l1; m2,b2 = l2; m3,b3 = l3
return (b3-b1)*(m1-m2) <= (b2-b1)*(m1-m3)
dq = deque() # (m, b), 傾き降順
for j in range(N):
if j > 0:
while len(dq) >= 2:
m0,b0 = dq[0]; m1,b1 = dq[1]
if m0*X[j]+b0 >= m1*X[j]+b1:
dq.popleft()
else:
break
m, b = dq[0]
dp[j] = m*X[j] + b + X[j]**2 + C
nm, nb = -2*X[j], dp[j] + X[j]**2
while len(dq) >= 2 and bad(dq[-2], dq[-1], (nm, nb)):
dq.pop()
dq.append((nm, nb))
print(dp[N-1])
solve()Step-by-Step 解説
1DP 式の立式と変形
$dp[0]=0$，$dp[j] = \min_{i < j}(dp[i] + (x_j-x_i)^2 + C)$ を展開し直線の形に変換する。
$dp[0]=0$，$dp[j] = \min_{i < j}(dp[i] + (x_j-x_i)^2 + C)$ を展開し直線の形に変換する。
2CHT のデータ構造
傾き降順のデックに直線を管理。クエリは前端が最適，追加時は後端の不要な直線を除去。
傾き降順のデックに直線を管理。クエリは前端が最適，追加時は後端の不要な直線を除去。
3bad 判定（整数演算）
交点比較を整数に変換して浮動小数点誤差を回避。
交点比較を整数に変換して浮動小数点誤差を回避。
4計算量
各直線はデックに1回追加・1回削除 → $O(N)$ 全体。
各直線はデックに1回追加・1回削除 → $O(N)$ 全体。
計算量
前処理: $O(1)$
CHT 全体: $O(N)$（傾き・クエリ単調のため）
合計: $O(N)$
CHT 全体: $O(N)$（傾き・クエリ単調のため）
合計: $O(N)$
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
| bad 判定で浮動小数点 | 除算を使う | 整数演算に変換 |
| デックの方向 | 最小 vs 最大の違い | 最小 → 傾き降順がデック前端 |
| j=0 でクエリを引く | dp[0] 初期化前 | if j > 0: でスキップ |
| C を1回だけ足す | 各移動に C が必要 | 各移動ごとに +C |
次のステップ
- 発展: クエリが単調でない場合の Li Chao Tree 版 CHT ($O(N \log N)$)
- 応用: WQS 二分探索（Aliens Trick）との組み合わせ