問題
長さ $N$ の数列を ちょうど $K$ 個の連続する非空部分列に分割する。各部分列 $[l, r]$（$r-l+1$ 個の要素を含む）のコストを $\text{cost}(l,r) = (r-l+1)^2$（長さの2乗）とする。
$K$ 個の部分列の コスト総和を最小化 せよ。（数列の要素自体はコストに影響しない。）
制約
$1 \le K \le N \le 10^6$
時間制限: 3秒
入出力例
入力例 1
6 3
1 2 3 4 5 6出力例 1
12入力例 2
8 3
1 1 1 1 1 1 1 1出力例 2
22例1: $N=6, K=3$ → 均等分割 $[1,2],[3,4],[5,6]$: $4+4+4=12$。例2: $N=8, K=3$ → $[1..3],[4..5],[6..8]$: $9+4+9=22$。
概念図: 四辺形不等式と最適分割点の単調性
ヒント（段階的開示）
ヒント1: 方向性
DP で $dp[k][i]$ = 最初の $i$ 要素を $k$ グループに分けた最小コストとする。ナイーブ $O(KN^2)$ を最適化できないか。
ヒント2: アプローチ
$\text{cost}(j, i) = (i-j)^2$ は 四辺形不等式（QI: $w(a,c)+w(b,d) \le w(a,d)+w(b,c)$ for $a \le b \le c \le d$）を満たす。これにより最適分割点 $\text{opt}(i)$ が $i$ について単調非減少 → 分割統治 DP 最適化で各 $k$ のレイヤーを $O(N \log N)$ で処理。
ヒント3: 四辺形不等式の証明と実装骨格
$w(a,c)+w(b,d) \le w(a,d)+w(b,c)$（$a \le b \le c \le d$）:
$(c-a)^2+(d-b)^2 \le (d-a)^2+(c-b)^2$
展開: $c^2-2ac+a^2+d^2-2bd+b^2 \le d^2-2ad+a^2+c^2-2bc+b^2$
整理: $-2ac-2bd \le -2ad-2bc$ → $2(ad-ac-bd+bc) = 2(a-b)(d-c) \ge 0$ ✓（$a \le b, c \le d$ より）
$(c-a)^2+(d-b)^2 \le (d-a)^2+(c-b)^2$
展開: $c^2-2ac+a^2+d^2-2bd+b^2 \le d^2-2ad+a^2+c^2-2bc+b^2$
整理: $-2ac-2bd \le -2ad-2bc$ → $2(ad-ac-bd+bc) = 2(a-b)(d-c) \ge 0$ ✓（$a \le b, c \le d$ より）
def solve_layer(k, prev_dp, N):
new_dp = [float('inf')] * (N+1)
stack = [(k, N, k-1, N-1)]
while stack:
l, r, opt_lo, opt_hi = stack.pop()
if l > r: continue
mid = (l+r)//2
best, bopt = float('inf'), opt_lo
for j in range(opt_lo, min(opt_hi, mid-1)+1):
c = prev_dp[j] + (mid-j)**2
if c < best: best=c; bopt=j
new_dp[mid] = best
stack.append((l, mid-1, opt_lo, bopt))
stack.append((mid+1, r, bopt, opt_hi))
return new_dp模範解答 (Python)
import sys
input = sys.stdin.readline
def solve():
N, K = map(int, input().split())
_ = input() # 数列は使わない
INF = float('inf')
dp = [INF] * (N + 1)
dp[0] = 0
for k in range(1, K + 1):
new_dp = [INF] * (N + 1)
# 反復的な分割統治最適化
stack = [(k, N, k - 1, N - 1)]
while stack:
l, r, opt_lo, opt_hi = stack.pop()
if l > r:
continue
mid = (l + r) // 2
best = INF
best_opt = opt_lo
hi = min(opt_hi, mid - 1)
for j in range(opt_lo, hi + 1):
length = mid - j
c = dp[j] + length * length
if c < best:
best = c
best_opt = j
new_dp[mid] = best
stack.append((l, mid - 1, opt_lo, best_opt))
stack.append((mid + 1, r, best_opt, opt_hi))
dp = new_dp
print(dp[N])
solve()
Step-by-Step 解説
1DP の定式化
$dp[k][i]$ = 最初の $i$ 要素を $k$ グループに分けた最小コスト。遷移: $dp[k][i] = \min_{j < i}(dp[k-1][j] + (i-j)^2)$。ナイーブ $O(KN^2)$。
$dp[k][i]$ = 最初の $i$ 要素を $k$ グループに分けた最小コスト。遷移: $dp[k][i] = \min_{j < i}(dp[k-1][j] + (i-j)^2)$。ナイーブ $O(KN^2)$。
2四辺形不等式の確認
$w(j,i) = (i-j)^2$ が QI を満たすことを証明: $w(a,c)+w(b,d) \le w(a,d)+w(b,c)$ は $(a-b)(d-c) \ge 0$ に帰着（$a \le b \le c \le d$ より成立）。
$w(j,i) = (i-j)^2$ が QI を満たすことを証明: $w(a,c)+w(b,d) \le w(a,d)+w(b,c)$ は $(a-b)(d-c) \ge 0$ に帰着（$a \le b \le c \le d$ より成立）。
3最適分割点の単調性
QI → $\text{opt}(i)$ は $i$ について単調非減少。つまり $\text{opt}(l) \le \text{opt}(mid) \le \text{opt}(r)$（$l \le mid \le r$）。
QI → $\text{opt}(i)$ は $i$ について単調非減少。つまり $\text{opt}(l) \le \text{opt}(mid) \le \text{opt}(r)$（$l \le mid \le r$）。
4分割統治最適化
$mid = (l+r)/2$ に対して $\text{opt}(mid)$ を $[\text{opt\_lo}, \text{opt\_hi}]$ で線形探索。左半分は $[\text{opt\_lo}, \text{opt}(mid)]$、右半分は $[\text{opt}(mid), \text{opt\_hi}]$ で再帰。各レベルで合計 $O(N)$ → 全体 $O(N \log N)$ per layer。
$mid = (l+r)/2$ に対して $\text{opt}(mid)$ を $[\text{opt\_lo}, \text{opt\_hi}]$ で線形探索。左半分は $[\text{opt\_lo}, \text{opt}(mid)]$、右半分は $[\text{opt}(mid), \text{opt\_hi}]$ で再帰。各レベルで合計 $O(N)$ → 全体 $O(N \log N)$ per layer。
5均等分割の性質
$\sum l_i^2$（$\sum l_i = N$, 各 $l_i \ge 1$）の最小化は、長さをなるべく均等にすること（凸関数の性質）。$\lfloor N/K \rfloor$ と $\lceil N/K \rceil$ の組み合わせが最適。
$\sum l_i^2$（$\sum l_i = N$, 各 $l_i \ge 1$）の最小化は、長さをなるべく均等にすること（凸関数の性質）。$\lfloor N/K \rfloor$ と $\lceil N/K \rceil$ の組み合わせが最適。
計算量
各 $k$ のレイヤー: $O(N \log N)$
全体: $O(KN \log N)$
SMAWK による改善: $O(KN)$（各レイヤー $O(N)$）
空間: $O(N)$（dp 配列 1 本を更新）
全体: $O(KN \log N)$
SMAWK による改善: $O(KN)$（各レイヤー $O(N)$）
空間: $O(N)$（dp 配列 1 本を更新）
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
opt の上限を mid にしてしまう | $j < i$ が必要 | min(opt_hi, mid - 1) が正しい上限 |
| K 層目のコスト計算で dp が未更新 | 前層の dp を上書き | new_dp を別配列で作り完成後に dp = new_dp |
| スタックオーバーフロー | $N=10^6$ での深い再帰 | 反復 DFS（明示的スタック）で実装 |
| 四辺形不等式の確認不足 | 単調性が成立しないコスト関数に誤用 | 必ず $w(a,c)+w(b,d) \le w(a,d)+w(b,c)$ を証明 |
次のステップ
- 発展問題: コスト関数が累積和依存（$w(l,r) = (A_r - A_{l-1})^2$）の場合への拡張
- 関連: Knuth の最適化（区間 DP の特殊形）との比較
- 応用: SMAWK アルゴリズムを実装して $O(KN)$ に改善する