問題
N 個の工場（位置 $x_i$、需要 $d_i$、$x_i$ は昇順）を K 個の倉庫に割り当て、「需要 × 最近傍倉庫までの距離の二乗」の総和を最小化。倉庫位置は実数可。
制約
$1 \le K \le N \le 10^5$
$0 \le x_i \le 10^9$（昇順）
$1 \le d_i \le 10^4$
入出力例
入力例 1
6 2
1 2
3 3
5 1
8 4
10 2
12 3出力例 1
14ヒント (段階的開示)
ヒント1: 方向性
工場は1次元昇順なので倉庫の担当区間は連続。N 個を K グループに分割する1D1D DP。
ヒント2: アプローチ
最適倉庫位置は加重平均。$\text{cost} = \sum d_i x_i^2 - (\sum d_i x_i)^2 / \sum d_i$ を累積和で O(1)。CHT / SMAWK / Divide&Conquer DP で高速化。
ヒント3: 誘導
四辺形不等式が成立 → 最適分割点が単調 → Divide&Conquer DP で各層 O(N log N)。
模範解答 (Python)
import sys
input = sys.stdin.readline
def solve():
N, K = map(int, input().split())
xs, ds = [], []
for _ in range(N):
x, d = map(int, input().split())
xs.append(x); ds.append(d)
sw = [0] * (N + 1)
swx = [0] * (N + 1)
swx2 = [0] * (N + 1)
for i in range(N):
sw[i+1] = sw[i] + ds[i]
swx[i+1] = swx[i] + ds[i] * xs[i]
swx2[i+1] = swx2[i] + ds[i] * xs[i] * xs[i]
def cost(l, r):
W = sw[r+1] - sw[l]
WX = swx[r+1] - swx[l]
WX2 = swx2[r+1] - swx2[l]
if W == 0:
return 0
return WX2 - WX * WX / W
INF = float('inf')
dp = [INF] * (N + 1)
dp[0] = 0
for k in range(K):
new_dp = [INF] * (N + 1)
new_dp[0] = 0
def dc(lo, hi, opt_lo, opt_hi):
if lo > hi:
return
mid = (lo + hi) // 2
best_cost = INF
best_opt = opt_lo
for m in range(opt_lo, min(opt_hi, mid - 1) + 1):
if dp[m] == INF:
continue
c = dp[m] + cost(m, mid - 1)
if c < best_cost:
best_cost = c
best_opt = m
new_dp[mid] = best_cost
dc(lo, mid - 1, opt_lo, best_opt)
dc(mid + 1, hi, best_opt, opt_hi)
dc(1, N, 0, N - 1)
dp = new_dp
print(int(dp[N]))
solve()Step-by-Step 解説
1コスト関数
加重平均 $x^* = \sum d_i x_i / \sum d_i$。最小コスト = $\sum d_i x_i^2 - (\sum d_i x_i)^2 / \sum d_i$。
加重平均 $x^* = \sum d_i x_i / \sum d_i$。最小コスト = $\sum d_i x_i^2 - (\sum d_i x_i)^2 / \sum d_i$。
2DP 定式化
$dp[k][i] = \min_{j<i}(dp[k-1][j] + \text{cost}(j+1, i))$。素朴 $O(N^2 K)$。
$dp[k][i] = \min_{j<i}(dp[k-1][j] + \text{cost}(j+1, i))$。素朴 $O(N^2 K)$。
3Divide & Conquer DP
四辺形不等式で opt 単調 → 各層 $O(N \log N)$、全体 $O(NK \log N)$。
四辺形不等式で opt 単調 → 各層 $O(N \log N)$、全体 $O(NK \log N)$。
4四辺形不等式の確認
加重分散は凸性から自動的に成立。
加重分散は凸性から自動的に成立。
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
| opt 範囲ミス | lo/hi と opt の対応混同 | 左 (opt_lo, best_opt), 右 (best_opt, opt_hi) |
| 浮動小数点の精度 | 大きい数値の除算 | 整数演算なら分数管理 |
| K=0 のエッジケース | 初期 dp が使われる | dp[0]=0, それ以外 INF |
次のステップ
- Convex Hull Trick による O(NK) 最適化