問題
数列 $A_1, A_2, \ldots, A_N$ が与えられる。ちょうど $K$ 個の「切断点」を選び、数列を $K+1$ 個の連続部分列に分割する。各部分列のコストは「最大値 − 最小値」とする。総コストを最小化せよ。
制約
$2 \le K \le N-1 \le 2 \times 10^5$
$0 \le A_i \le 10^9$
時間制限: 2sec / メモリ: 256MB
入出力例
入力例 1
7 2
3 1 4 1 5 9 2出力例 1
7概念図: WQS二分探索の原理
ヒント（段階的開示）
ヒント1: 方向性
ちょうど $K$ 個の切断という「個数制約」を扱うため、ペナルティ法（Alien's Trick / WQS 二分探索）を使う。切断1回あたりコスト $\lambda$ を課し、制約なしの最適 $K$ が整数的に単調になる性質を利用する。
ヒント2: アプローチ
- $f(\lambda) = $ 「各切断にペナルティ $\lambda$ を加えた場合の最小コスト」を計算。
- $k(\lambda) \ge K$ となる最大の $\lambda$ を二分探索。
- $g(\lambda) = f(\lambda) + K \cdot \lambda$ が最終答え（双対性）。
- 内部DPはSparse Tableで区間max/minをO(1)にし、DP遷移O(N²)→O(N log N)。
ヒント3: 実装骨格
# ペナルティ lam でのDP
def dp_with_penalty(A, lam):
n = len(A)
dp = [inf] * (n + 1)
cnt = [0] * (n + 1) # 切断数
dp[0] = 0
for i in range(1, n + 1):
for j in range(i):
cost = query_range(j, i) # max-min of A[j..i-1]
penalty = lam if j > 0 else 0
val = dp[j] + cost + penalty
if val < dp[i]:
dp[i] = val
cnt[i] = cnt[j] + (1 if j > 0 else 0)
return dp[n], cnt[n]
# WQS 二分探索
lo, hi = -10**9, 10**9
while lo < hi:
mid = (lo + hi) // 2
_, k = dp_with_penalty(A, mid)
if k >= K: lo = mid + 1
else: hi = mid
ans = dp_with_penalty(A, lo-1)[0] + K * (lo-1)模範解答 (Python)
import sys
from math import inf, log2, floor
input = sys.stdin.readline
def solve():
N, K = map(int, input().split())
A = list(map(int, input().split()))
# Sparse Table for range max/min in O(1)
LOG = max(1, floor(log2(N)) + 1) if N > 1 else 1
smax = [A[:]] + [[0]*N for _ in range(LOG-1)]
smin = [A[:]] + [[0]*N for _ in range(LOG-1)]
for k in range(1, LOG):
for i in range(N - (1 << k) + 1):
smax[k][i] = max(smax[k-1][i], smax[k-1][i + (1 << (k-1))])
smin[k][i] = min(smin[k-1][i], smin[k-1][i + (1 << (k-1))])
def query(l, r): # [l, r) のmax-min
if l >= r: return 0
length = r - l
k = floor(log2(length))
return (max(smax[k][l], smax[k][r-(1< 0 else 0)
val = dp[j] + c
if val < dp[i] or (val == dp[i] and
cnt[j] + (1 if j > 0 else 0) > cnt[i]):
dp[i] = val
cnt[i] = cnt[j] + (1 if j > 0 else 0)
return dp[N], cnt[N]
lo, hi = -10**9, 10**9
while lo < hi:
mid = (lo + hi) // 2
_, k = dp_with_penalty(mid)
if k >= K:
lo = mid + 1
else:
hi = mid
lam = lo - 1
cost, _ = dp_with_penalty(lam)
print(cost + K * lam)
solve()
Step-by-Step 解説
1問題の凸性確認
$h(K)$ = ちょうど $K$ 回切断した最小コストは $K$ に関して凸関数（限界利益が単調非増加）。この凸性が Alien's Trick の前提条件。
$h(K)$ = ちょうど $K$ 回切断した最小コストは $K$ に関して凸関数（限界利益が単調非増加）。この凸性が Alien's Trick の前提条件。
2ペナルティ法の双対
切断1回あたりペナルティ $\lambda$ を加えた問題 $f(\lambda)$ の最適切断数 $k(\lambda)$ は $\lambda$ について単調非増加。
切断1回あたりペナルティ $\lambda$ を加えた問題 $f(\lambda)$ の最適切断数 $k(\lambda)$ は $\lambda$ について単調非増加。
3二分探索の設計
$k(\lambda) \ge K$ を満たす最大の整数 $\lambda$ を探す。この $\lambda^*$ において $g = f(\lambda^*) + K \cdot \lambda^*$ が元の問題の答え。
$k(\lambda) \ge K$ を満たす最大の整数 $\lambda$ を探す。この $\lambda^*$ において $g = f(\lambda^*) + K \cdot \lambda^*$ が元の問題の答え。
4Sparse Table
区間 $[l, r)$ の max, min を $O(1)$ で求めるための前処理。$k$ 段目: $2^k$ 幅の区間の max/min を保持。
区間 $[l, r)$ の max, min を $O(1)$ で求めるための前処理。$k$ 段目: $2^k$ 幅の区間の max/min を保持。
5計算量と最適化
現在のDP遷移は $O(N^2)$。実際の競技では SMAWK または Monotone Minima を用いて $O(N \log N)$ に改善可能。
現在のDP遷移は $O(N^2)$。実際の競技では SMAWK または Monotone Minima を用いて $O(N \log N)$ に改善可能。
計算量
Sparse Table 構築: $O(N \log N)$
区間クエリ: $O(1)$
各 $\lambda$ でのDP: $O(N^2)$（SMAWK使用で $O(N \log N)$）
二分探索ループ: $O(\log(\max A))$ 回
合計: $O(N^2 \log(\max A))$（素朴版）/ $O(N \log N \log(\max A))$（最適版）
区間クエリ: $O(1)$
各 $\lambda$ でのDP: $O(N^2)$（SMAWK使用で $O(N \log N)$）
二分探索ループ: $O(\log(\max A))$ 回
合計: $O(N^2 \log(\max A))$（素朴版）/ $O(N \log N \log(\max A))$（最適版）
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
| 切断数 vs 部分列数のずれ | $K$ 切断 = $K+1$ 部分列 | ペナルティは切断ごとに加算 |
| 二分探索の境界 off-by-one | $k(\lambda)$ の単調性の向き | lo / hi を慎重に設定 |
| 同値 $k(\lambda) = K$ の処理 | 複数の $\lambda$ で $k=K$ | cnt を tie-break に使う |
| Sparse Table の log 計算 | 浮動小数点誤差 | floor(log2(length)) を正確に |
次のステップ
- 発展問題: WQS + CHT（Convex Hull Trick）で $O(N \log N)$ に高速化
- 類題: USACO 2016 December Platinum "Landscaping"
- 応用: K個のクラスタへの分割問題（k-means的な離散最適化）