問題
N個の要素からなる数列 A が与えられる。任意の要素を値 x に変更するコスト $|A[i] - x|$ で、結果が非減少列になるよう最小コストを求めよ。さらに最大K個を「固定」できる場合、どのK個を固定すると最終コストが最大化されるか答えよ。
制約
$N \le 2 \times 10^5$
$1 \le A[i] \le 10^9$
$0 \le K \le N$
入出力例
入力例 1
5 1
3 1 4 1 5出力例 1
固定なし最小コスト: 3
1個固定時の最大化コスト: 4ヒント (段階的開示)
ヒント1: 方向性
Slope Trick は「絶対値和の最小化」をDP関数の折れ線として管理する手法。傾きの変化点（折れ目）のみで表現。
ヒント2: アプローチ
最大ヒープ（左側の折れ目）と最小ヒープ（右側の折れ目）を管理。各要素追加時にヒープを O(log N) で更新。
ヒント3: 誘導
for a in A:
heapq.heappush(left, -a)
top = -left[0]
if top > a:
cost += top - a
heapq.heappop(left)
heapq.heappush(left, -a)模範解答 (Python)
import sys
import heapq
input = sys.stdin.readline
def slope_trick_isotonic(A):
left = []
cost = 0
for a in A:
heapq.heappush(left, -a)
top = -left[0]
if top > a:
cost += top - a
heapq.heappop(left)
heapq.heappush(left, -a)
return cost
def main():
N, K = map(int, input().split())
A = list(map(int, input().split()))
base_cost = slope_trick_isotonic(A)
print(f"固定なし最小コスト: {base_cost}")
if K == 0:
print(f"K=0なので最小コストはそのまま: {base_cost}")
return
diffs = []
for i in range(N):
A_without = A[:i] + A[i+1:]
cost_without = slope_trick_isotonic(A_without) if A_without else 0
diffs.append((base_cost - cost_without, i))
diffs.sort(reverse=True)
fixed_indices = sorted([diffs[j][1] for j in range(K)])
final_cost = base_cost + sum(d for d, _ in diffs[:K])
print(f"固定すべきインデックス: {fixed_indices}")
print(f"固定後の最大コスト: {final_cost}")
main()Step-by-Step 解説
1Slope Trick の基本概念
DP[i](x) = A[0..i]を処理して、A[i]の最終値を x にするときの最小コスト。区分線形関数（折れ線）であり、折れ目のみをヒープで管理。
DP[i](x) = A[0..i]を処理して、A[i]の最終値を x にするときの最小コスト。区分線形関数（折れ線）であり、折れ目のみをヒープで管理。
2非減少制約の処理
各 A[i] 処理時、折れ目に A[i] を追加。最大折れ目が A[i] より大きければコストを加算し折れ目を A[i] に押し戻す。
各 A[i] 処理時、折れ目に A[i] を追加。最大折れ目が A[i] より大きければコストを加算し折れ目を A[i] に押し戻す。
3K要素固定の最大化
最も全体コストを増加させる要素をK個選ぶ貪欲法。
最も全体コストを増加させる要素をK個選ぶ貪欲法。
4双方向DPの活用
前方向・後方向 Slope Trick の結果を組み合わせて各要素を固定した場合の影響を計算。
前方向・後方向 Slope Trick の結果を組み合わせて各要素を固定した場合の影響を計算。
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
| ヒープの符号 | 最大ヒープをPythonで実現 | 負値でheapqを使う |
| 折れ目の数 | 1要素追加で折れ目が最大1つ増える | ポップとプッシュで個数管理 |
| 非増加制約 | 配列反転で非減少と同じ処理 | B = [-x for x in reversed(A)] |
次のステップ
- 発展: Slope Trick + セグメント木（動的追加・削除の高速化）
- 応用: 区間の非減少制約付き最小コスト編集