Day 103-Q1 — Slope Trick（凸区分線形関数のDP）

2026-07-26 赤色 Master / Phase 8+ ★★★★★★★★☆ 非減少列への最小コスト変換

問題

$N$ 冊の本が一列に並んでおり、左から $i$ 番目の本の高さは $A_i$。本の並び替えはできないが、高さを $A_i$ から $B_i$ に変えることができ、コストは $|A_i - B_i|$。$B_1 \le B_2 \le \dots \le B_N$（非減少）になるようにするとき、コスト合計 $\sum|A_i-B_i|$ の最小値を求めよ。

$f_i(x)=$「$B_i=x$として最初の$i$冊を非減少に整形する最小コスト」は $x$ について下に凸な区分線形関数になる。この関数を陽に持たず、傾きの変化点だけを最大値ヒープで管理する手法を Slope Trick と呼ぶ。今回は非減少制約の特殊性から、左側の傾き変化点（最大値ヒープ）だけで解ける簡潔な形が使える。

入力形式

N
A_1 A_2 ... A_N

制約

$1 \le N \le 2\times10^5$
$0 \le A_i \le 10^9$
すべて整数
$B_i$ は整数でよい

入出力例

入力例1

5
3 1 4 1 5

出力例1

5

$B=(1,1,4,4,5)$ とすると $|3-1|+|1-1|+|4-4|+|1-4|+|5-5|=2+0+0+3+0=5$ が最小。

入力例2

5
5 4 3 2 1

出力例2

6

完全降順の列は全要素を中央値3にそろえるのが最適：$2+1+0+1+2=6$。

概念図

A=[3,1,4,1,5] → 非減少列 B=[1,1,4,4,5] への変形 0 cost 2 cost 3 i=1 i=2 i=3 i=4 i=5 オレンジ=元のA teal=非減少に整形後のB

ヒント（段階的開示）

ヒント1: 方向性
もし「全要素を同じ1つの値にそろえて$\sum|A_i-x|$を最小化せよ」なら中央値を使えばよいと知っているかもしれない。しかし今回は"非減少"という部分的な制約であり、列全体を1つの値にする必要はない。左から順に確定させ、局所的な違反だけをその場で直す貪欲な方針を考えよう。
ヒント2: アプローチ
左から要素を処理する際「これまでに割り当てた値の中での最大値」を管理する最大値ヒープを持つ。新しい要素$a$を追加するとき、まず$a$をヒープに積む。もし現在の最大値$m$が$a$より大きければ非減少制約に違反するので、その山を$a$の高さまで削り、コスト$(m-a)$を支払う（popしてから$a$を積み直す）。
ヒント3: 誘導（コード骨格） 
import heapq

heap = []  # 最大値ヒープ（符号反転）
ans = 0
for a in A:
    heapq.heappush(heap, -a)
    if -heap[0] > a:
        top = -heapq.heappop(heap)
        ans += top - a
        heapq.heappush(heap, -a)
print(ans)

この単純な貪欲が最適解を与えることは、凸関数のSlope Trickにおける「左側breakpoint集合のマージ」として正当化される。

模範解答 (Python)

import sys
import heapq


def solve():
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    a = list(map(int, data[1:1 + n]))

    heap = []  # 最大値を素早く取り出すため符号反転して最小ヒープとして使う
    ans = 0
    for x in a:
        heapq.heappush(heap, -x)
        if -heap[0] > x:
            top = -heapq.heappop(heap)
            ans += top - x
            heapq.heappush(heap, -x)

    print(ans)


solve()
計算量: $O(N \log N)$（各要素につきヒープ操作が高々定数回）。

Step-by-Step 解説

1凸関数のDPとして捉える
$f_i(x)=|A_i-x|+\min_{y\le x}f_{i-1}(y)$。累積最小を取る操作は凸性を保つ。
2breakpointの集合として管理
非減少制約により左側（傾きが負の部分）のbreakpointだけを最大値ヒープで管理すれば十分。
3新要素の追加とヒープ更新
$a$を積み、現在の最大値が$a$を超えていればその分を$a$まで下げてコストを精算する。
4答えの算出
$N$回のループ終了後の`ans`が最小コスト。$B$の具体的な値自体は不要。

よくあるミス

ミス原因正しい書き方
全要素を1つの中央値にそろえてしまう「全体を1つの値にする」問題と混同非減少制約は部分的なので局所的な違反だけを直す貪欲法を使う
`heapq`が最小ヒープであることを忘れるPythonの`heapq`は最小ヒープのみ対応最大値ヒープが欲しい場合は符号反転して積み、取り出す時も戻す
違反時にpopのみでpushを忘れる削った山の代表値をヒープに戻し忘れるpopした後は必ず`heapq.heappush(heap, -x)`で積み直す
コストを`abs(top-x)`にする条件分岐内では`top>x`が保証されているのに絶対値を取ってしまう条件内では単に`top-x`（正の値）でよい

次のステップ

  • 発展: 「非減少」以外の制約（差が一定範囲内など）への一般化（Slope Trickの一般形：左右両方のheapを持つ）
  • 発展: クエリごとに要素を追加・削除しながらオンラインで最小コストを answer するデータ構造への拡張
  • 次回予告: 桁DP × Aho-Corasickオートマトン（禁止パターンを含まない整数の個数え上げ、$N\le10^{18}$）

自己評価

自分の回答

気づき・メモ