問題
$N$ 個の工場が横一列に並んでおり、工場 $i$ の位置は $x_i$（$x_1 < x_2 < \cdots < x_N$）、需要量は $d_i$ である。
これらを 連続する区間 に分割し、各区間に 1 つの倉庫を配置する。区間 $[l, r]$ に対するコストは：
$$\text{cost}(l, r) = \left(\sum_{i=l}^{r} d_i\right) \cdot \min_{z} \sum_{i=l}^{r} d_i |x_i - z|$$（$z$ は連続値、最適値は加重中央値）
$N$ 個の工場を ちょうど $K$ 区間 に分割するときの全区間コストの総和の最小値を求めよ。
制約
| パラメータ | 範囲 |
|---|---|
| $N$ | $1 \le K \le N \le 3000$ |
| $x_i$ | $1 \le x_i \le 10^9$（狭義単調増加） |
| $d_i$ | $1 \le d_i \le 10^9$ |
入出力例
入力例 1
5 2
1 2
3 1
5 3
7 2
9 1出力例 1
14最適分割: [1,2,3] と [4,5] 、または [1,2] と [3,4,5]。各区間の加重中央値でコスト計算。
概念図: 加重中央値とコスト計算
ヒント（段階的開示）
ヒント1: 方向性
区間コスト $\text{cost}(l, r)$ を事前計算（$O(N^2)$）し、$dp[k][i] = $ 最初の $i$ 工場を $k$ 区間に分けた最小コストとして漸化式を解く。$\text{cost}(l, r)$ の内側の最小化は加重中央値によって解析的に解ける。
ヒント2: アプローチ
- 加重中央値: 累積需要が総需要の半分以上になる最初の工場インデックス（二分探索で $O(\log N)$）
- 区間コストは prefix sum で $O(1)$ 計算可能
- $O(KN^2)$ DP で $N=3000$ は約 $2.7 \times 10^{10}$ → TLE。四辺形不等式による最適化が必要
ヒント3: prefix sum によるコスト計算
# prefix sum の準備
pd = [0]*(N+2) # prefix demand
pdx = [0]*(N+2) # prefix demand * x
for i in range(1, N+1):
pd[i] = pd[i-1] + D[i]
pdx[i] = pdx[i-1] + D[i]*X[i]
def weighted_median_cost(l, r):
total = pd[r] - pd[l-1]
half = (total + 1) // 2
# 二分探索で加重中央値 m を探す
lo, hi = l, r
while lo < hi:
mid = (lo + hi) // 2
if pd[mid] - pd[l-1] >= half: hi = mid
else: lo = mid + 1
m = lo # 加重中央値インデックス
# 左コスト: x_m * Σd_i(i<=m) - Σd_i*x_i(i<=m)
# 右コスト: Σd_i*x_i(i>m) - x_m * Σd_i(i>m)
ld = pd[m]-pd[l-1]; ldx = pdx[m]-pdx[l-1]
rd = pd[r]-pd[m]; rdx = pdx[r]-pdx[m]
inner = X[m]*ld - ldx + rdx - X[m]*rd
return total * inner模範解答 (Python)
import sys
input = sys.stdin.readline
def solve():
N, K = map(int, input().split())
X = [0]*(N+1); D = [0]*(N+1)
for i in range(1, N+1):
X[i], D[i] = map(int, input().split())
pd = [0]*(N+2); pdx = [0]*(N+2)
for i in range(1, N+1):
pd[i] = pd[i-1] + D[i]
pdx[i] = pdx[i-1] + D[i]*X[i]
def cost(l, r):
total = pd[r] - pd[l-1]
half = (total + 1) // 2
lo, hi = l, r
while lo < hi:
mid = (lo+hi)>>1
if pd[mid]-pd[l-1] >= half: hi = mid
else: lo = mid+1
m = lo
ld = pd[m]-pd[l-1]; ldx = pdx[m]-pdx[l-1]
rd = pd[r]-pd[m]; rdx = pdx[r]-pdx[m]
inner = X[m]*ld - ldx + rdx - X[m]*rd
return total * inner
INF = float('inf')
prev = [INF]*(N+1); prev[0] = 0
for k in range(1, K+1):
curr = [INF]*(N+1)
opt = [0]*(N+2) # 分割統治用（四辺形不等式）
def dc(l, r, opt_l, opt_r):
if l > r: return
mid = (l+r)>>1
best = INF; best_j = opt_l
for j in range(opt_l, min(opt_r, mid-1)+1):
if prev[j] == INF: continue
v = prev[j] + cost(j+1, mid)
if v < best:
best = v; best_j = j
curr[mid] = best; opt[mid] = best_j
dc(l, mid-1, opt_l, best_j)
dc(mid+1, r, best_j, opt_r)
dc(k, N, k-1, N)
prev = curr
print(prev[N])
solve()
Step-by-Step 解説
1加重中央値の計算
区間 $[l, r]$ の最適倉庫位置は加重中央値。prefix sum + 二分探索で $O(\log N)$ に求める。最適 $z$ の条件: 左側の総需要 $\ge$ 右側の総需要。
区間 $[l, r]$ の最適倉庫位置は加重中央値。prefix sum + 二分探索で $O(\log N)$ に求める。最適 $z$ の条件: 左側の総需要 $\ge$ 右側の総需要。
2コストを prefix sum で O(1) に
$\sum d_i |x_i - z|$ = 左側（$X[m] \cdot \sum d_i - \sum d_i x_i$）+ 右側（$\sum d_i x_i - X[m] \cdot \sum d_i$）を prefix sum で計算。さらに外の因子 $(\sum d_i)$ を掛ける。
$\sum d_i |x_i - z|$ = 左側（$X[m] \cdot \sum d_i - \sum d_i x_i$）+ 右側（$\sum d_i x_i - X[m] \cdot \sum d_i$）を prefix sum で計算。さらに外の因子 $(\sum d_i)$ を掛ける。
3四辺形不等式による分割統治最適化
$\text{cost}(l, r)$ が四辺形不等式 $C(a,c)+C(b,d) \le C(a,d)+C(b,c)$ を満たすとき、DP の最適分割点が単調になる。分割統治法（SMAWK的）で $O(KN \log N)$。
$\text{cost}(l, r)$ が四辺形不等式 $C(a,c)+C(b,d) \le C(a,d)+C(b,c)$ を満たすとき、DP の最適分割点が単調になる。分割統治法（SMAWK的）で $O(KN \log N)$。
4WQS二分探索（Alien's Trick）
$K$ の制約を $\lambda$ ペナルティで除去する方法。$\lambda$ を二分探索し $O(N \log N \log V)$ に削減可能（本解答は分割統治 $O(KN \log N)$）。
$K$ の制約を $\lambda$ ペナルティで除去する方法。$\lambda$ を二分探索し $O(N \log N \log V)$ に削減可能（本解答は分割統治 $O(KN \log N)$）。
計算量
コスト計算: $O(\log N)$ per call
分割統治DP（各 $k$）: $O(N \log N)$
全体: $O(KN \log N)$ — $K, N \le 3000$ で約 $3 \times 10^7$
素朴DP: $O(KN^2) = O(2.7 \times 10^{10})$ → TLE
分割統治DP（各 $k$）: $O(N \log N)$
全体: $O(KN \log N)$ — $K, N \le 3000$ で約 $3 \times 10^7$
素朴DP: $O(KN^2) = O(2.7 \times 10^{10})$ → TLE
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
| 加重中央値の条件を $>$ にする | オフバイワン | >= half |
| コストに total を掛け忘れ | 問題定義の読み違い | total * inner |
| 四辺形不等式の確認を省略 | 最適化が正しくない | 小ケースで手計算して検証 |
| 分割統治の opt 範囲ミス | opt_l > mid になりうる | j <= min(opt_r, mid-1) |
次のステップ
- 発展問題: $K$ を WQS 二分探索（Alien's Trick）で除去し $O(N \log N \log V)$ に
- 関連: 1次元 $k$-median 問題との等価性
- 応用: Li Chao Tree を用いた CHT 適用（傾きが単調な場合 $O(N \log N)$）