問題
数直線上の整数点を動く 1 人のプレイヤーがいる。時刻 $0$ に位置 $0$ にいる。時刻が 1 進むごとに位置を高々 1（$-1,0,+1$）しか動かせない（位置は整数）。
$i=1,\dots,N$ について、時刻 $T_i$ に位置 $X_i$ へ旗が立つ。時刻 $T_i$ にいた位置を $p_i$ とすると、費用 $|p_i-X_i|$ がかかる。費用の総和 $\sum_{i=1}^{N}|p_i-X_i|$ の最小値を求めよ。
入力形式
N
T_1 X_1
...
T_N X_N制約
| # | 条件 |
|---|---|
| 1 | $1\le N\le 2\times10^5$ |
| 2 | $1\le T_1<T_2<\dots<T_N\le10^9$ |
| 3 | $-10^9\le X_i\le10^9$ |
| 4 | 入力はすべて整数 |
入出力例
入力例1
3
1 5
2 -3
10 0出力例1
7（時刻 1 では $|p_1|\le1$ なので旗 5 まで 4 以上離れる。時刻 2 の旗 $-3$ へは、たとえば $p_1=-1,p_2=-2$ で費用 $6+1=7$。時刻 10 の旗 0 には余裕で戻れる）
入力例2
2
3 3
4 -3出力例2
5（時刻 3 に位置 3 へ着くのが精一杯で、時刻 4 には位置 2 まで戻れて $|2-(-3)|=5$。始点が自由なら 0 で済むので、「時刻 0 は位置 0」の固定が効いている例）
背景と出典
「凸関数を傾きの変わる点（折れ点）の列で持ち、左側を最大ヒープ・右側を最小ヒープで管理する」方法は日本の競プロで Slope Trick と呼ばれる。窓つきの移動制約の形は、私の記憶では AtCoder ABC217 H（Snuketoon）に近いが、問題文・制約は未確認で、本ファイルの設定は自分で決めたもの（始点を 0 に固定する点が違うと思われる）。本セッションでは外部資料を開いていない。正しさの根拠は、全位置を持つ素朴 DP との照合（下の検証ログ）。
概念図
ヒント（クリックで段階的に開示）
ヒント1（方向性）
$f_i(x)$ = 「時刻 $T_i$ に位置 $x$ にいるときの、ここまでの最小費用」とおく。移動制約は $f_i(x)=\min_{|y-x|\le d}f_{i-1}(y)+|x-X_i|$（$d=T_i-T_{i-1}$）。位置の範囲は $10^9$ 以上あるので、位置ごとの表は持てない。
ヒント2（アプローチ）
$f$ は常に凸（凸関数への $|x-a|$ の加算と、窓の最小はどちらも凸を保つ）。凸な折れ線は「傾きが 1 ずつ変わる点」の並びで表せる。窓の最小 $\min_{|y-x|\le d}$ は、最小値を取る区間を左右に $d$ ずつ広げるだけで、傾きが負の側が左へ $d$、正の側が右へ $d$ ずれる。
ヒント3（誘導）
左の折れ点（傾きが負の側）を最大ヒープ $L$、右の折れ点を最小ヒープ $R$ に入れ、$L$ には全体の足し込み量 addL、$R$ には addR を持つ。$|x-a|$ を足すときは 2 段階: $(x-a)^+$ を足す → 最小値に $\max(0,\ \mathrm{top}(L)-a)$ を足して $a$ を $L$ に入れ、$L$ の最大を $R$ へ移す。次に $(a-x)^+$ を足す → 対称。始点が $0$ に固定される分は、初期に折れ点 $0$ を $N+1$ 個ずつ両方のヒープに入れて「傾き $\pm(N+1)$ の壁」にする。
模範解答 (Python)
模範解答を表示する（まず自力で解いてから）
import sys
from heapq import heappush, heappop
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0])
# f(x): いまの時刻に位置 x にいる場合の、ここまでの最小コスト（凸）
# 左の折れ点 L（最大ヒープ、符号反転で保持）、右の折れ点 R（最小ヒープ）。
# 時刻 0 は x=0 に固定なので、傾き ±(n+1) の「壁」を折れ点 0 を n+1 個ずつ置いて表す
L = [0] * (n + 1)
R = [0] * (n + 1)
addL = 0 # L の全折れ点にまとめて足す量
addR = 0 # R の全折れ点にまとめて足す量
ans = 0
prev_t = 0
for i in range(n):
t = int(data[1 + 2 * i])
x = int(data[2 + 2 * i])
d = t - prev_t
prev_t = t
addL -= d # min をとる窓 [-d,+d] で、左の折れ点は左へ d
addR += d # 右の折れ点は右へ d
# |p - x| を足す。 (p-x)^+ と (x-p)^+ を順に足す
lt = -L[0] + addL # L の最大
if lt > x:
ans += lt - x
heappush(L, -(x - addL))
v = -heappop(L) + addL # L の最大を R へ移す
heappush(R, v - addR)
rt = R[0] + addR # R の最小
if x > rt:
ans += x - rt
heappush(R, x - addR)
v = heappop(R) + addR # R の最小を L へ移す
heappush(L, -(v - addL))
print(ans)
main()計算量: $O(N\log N)$。実測（Python 3.14.7、M1 Mac）で $N=2\times10^5$、$|X_i|\le10^9$ のランダム入力が 0.53 s（$T_i$ が 1 ずつ増える最悪に近い入力でも 0.47 s）。
Step-by-Step 解説
$f_0(x)=0\ (x=0),\ +\infty\ (x\ne0)$。$f_i(x)=\min_{|y-x|\le T_i-T_{i-1}}f_{i-1}(y)+|x-X_i|$。答えは $\min_x f_N(x)$。$f_i$ は全て凸な折れ線で、傾きは整数。
凸関数 $f$ の最小値を取る区間を $[l,r]$ とする。$g(x)=\min_{|y-x|\le d}f(y)$ は、$[l-d,\ r+d]$ で最小値、その左では $f$ の左側（減少する部分）を左へ $d$ ずらした形、右では右側（増加する部分）を右へ $d$ ずらした形になる。つまり **左の折れ点は $-d$、右の折れ点は $+d$**。ヒープに入っている値を 1 つずつ書き換えず、addL -= d、addR += d と 1 回の足し算で済ませる。左右で別々のオフセットが必要なのが、通常の Slope Trick（全体に同じ量を足す）との違い。
$|x-a|=(x-a)^++(a-x)^+$。$(x-a)^+$ を足すと $a$ より右で傾きが 1 増える。最小値は、$L$ の最大 $\ell$ が $a$ より右にあれば $\ell-a$ だけ増える（$\max(0,\ell-a)$）。折れ点 $a$ が増えて傾きが 1 増えた分、$L$ の最大 1 個が負側から正側へ移るので、$a$ を $L$ に入れてから $L$ の最大を取り出して $R$ へ移す。$(a-x)^+$ は左右を入れ替えて同じ。
$f_0$ は $x=0$ 以外が $+\infty$。実際の傾きは高々 $N$（絶対値 1 を $N$ 回足すだけ）なので、折れ点 $0$ を $N+1$ 個ずつ置けば「傾き $N+1$ 以上の壁」と区別できない。壁の折れ点も窓の移動で左右にずれるので、時刻とともに壁の位置が $[-T,+T]$ に広がる。始点を自由にして壁を置かないと 500 件中 231 件で誤る（実測）。
ずらす量 $d$ を 0 にすると 493/500、右側だけずらして左側を動かさないと 393/500 で誤る（実測）。壁が 1 個だけだと 42/500、$N-1$ 個だと 13/500 で誤る（実測）。壁の個数は「傾きの上限 $N$ より 1 多い」ことが必要。
迷った他案と採らなかった理由
| 案 | 計算量 | 採否 | 理由 |
|---|---|---|---|
| 位置を全部持つ DP（$f$ の表） | $O(N\cdot T_N)$ | 検算用のみ | $T_N=10^9$ には不可。検算に使った |
| 位置を $X_i$ で圧縮した DP | $O(N^2)$ | 不採用 | 窓があると最適な位置の候補が $X_j\pm$（時刻差）の形で増え、圧縮した点数が $O(N^2)$ になりうると見て採らなかった（未検証） |
| 折れ点を平衡二分探索木に持つ | $O(N\log N)$ | 不採用 | 動くのは最大値・最小値と全体のずらしだけで、ヒープで足りる |
| Slope Trick（左右別オフセットのヒープ、本解） | $O(N\log N)$ | 採用 | 全位置 DP と 500 件全件一致 |
| 始点を自由にして壁を置かない | $O(N\log N)$ | 不採用 | 500 件中 231 件誤答（「時刻 0 は位置 0」を無視） |
前提が変わったら:
- 時刻ごとに動ける距離が違う（$|{\rm 移動}|\le v_i$）なら、$d=v_i$ をその区間の窓に置き換えるだけで同じ形
- **コストが $|x-a|$ 以外の凸関数**（$(x-a)^2$ など）なら折れ線ではなくなり、Slope Trick は使えない（Lagrange 乗数や凸最適化の枠）
- 位置が整数に限らないときも同じ解。折れ点は整数のままで、ずらす量が実数になるだけ
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
| 窓のずらしを 1 つのオフセットで済ます | 通常の Slope Trick の癖で全体に同じ量を足す | addL -= d と addR += d を別々に持つ（右のみ: 393/500 誤答） |
| 壁を置かず始点を自由にする | 初期状態の $+\infty$ を表せない | 折れ点 0 を $N+1$ 個ずつ置く（231/500 誤答） |
| 壁を 1 個にする | 「傾き無限大」を 1 個で表せると思う | 傾きの上限 $N$ を超える個数にする（1 個: 42/500、$N-1$ 個: 13/500 誤答） |
| $\max(0,\cdot)$ を付けず常に差を足す | $\ell\le a$ のとき最小値が増えないことを忘れる | if lt > x: ans += lt - x |
次のステップ
- 発展1: 各 $i$ で最適な位置 $p_i$ も復元する（ヒープを巻き戻す必要があり、Slope Trick の復元は一般に面倒。$f_i$ の最小点の区間を後ろ向きに辿る）
- 発展2: 動ける距離が時刻ごとに違い、かつ位置に下限・上限がある版（壁の位置を外から与える）
- 次回予告: 焦点帯 M1 の DP 最適化（Aliens）
検証ログ（本セッションで実行した数値）
- 素朴 DP との照合（実測）: 位置を $[-T_N,T_N]$ の全点で持つ DP と、$N\le8$、$d\le3$、$|X|\le8$ の 500 件でプログラム全体の出力が全件一致（答えが 0 の件は 30）
- 誤った方法（実測）: 始点自由（壁なし）231/500、移動量 0 のまま 493/500、右側だけずらす 393/500、壁 1 個 42/500、壁 $N-1$ 個 13/500 で誤答
- 入力例（実測）: 例 1 は 7、例 2 は 5（どちらも素朴 DP と一致）
- 実行時間（実測）: $N=2\times10^5$、$T_i$ の間隔 1〜3、$|X_i|\le10^9$ で 0.53 s。$T_i=i$ で 0.47 s
- 扱っていない範囲: 位置の復元、ABC217 H の原文との突き合わせ、$f_i$ が非凸になる場合（コストが凸でない・移動範囲が不連続）