Day 069-Q1 | Convex Hull Trick + スライディングウィンドウ最小値DP

問題

$N$ 個の区間 $[l_i, r_i]$（コスト $c_i = (r_i - l_i + 1)^2 + a_i$）を使い、座標 $1, 2, \ldots, M$ を全て被覆するコスト総和の最小値を求めよ。区間は $r_i$ の昇順にソート済み。

制約

パラメータ	範囲
$N$	$1 \le N \le 2 \times 10^5$
$M$	$1 \le M \le 10^9$
$l_i, r_i$	$1 \le l_i \le r_i \le M$
$a_i$	$0 \le a_i \le 10^9$

入出力例

入力例 1

出力例 1

区間[1,4]コスト=17、[2,7]コスト=36、[5,9]コスト=27、[8,10]コスト=10。最適: [1,4]+[8,10]=17+10=27 はM=10全体を被覆せず。[1,4]+[5,9]+[8,10]で1-4,5-9,8-10→全体被覆。コスト=(4²+1)+(5²+2)+(3²+1)=17+27+10=54。より小さい選択を探す。

概念図: スライディングウィンドウ最小値DP

ヒント（段階的開示）

ヒント1: 方向性

DP で $dp[j]$ = 座標 $j$ まで被覆する最小コストを定義。区間 $[l_i, r_i]$ を最後に使う場合の遷移は「$dp[l_i - 1]$ 以前の最小値 + $c_i$」。$M \le 10^9$ なので座標圧縮が必要。

ヒント2: アプローチ

遷移: $dp[r_i] = \min_{j \le l_i - 1} dp[j] + c_i$
$j$ の上限 $l_i - 1$ は必ずしも単調でないが、二分探索で対応可能
座標圧縮: 右端の値だけを圧縮してDPを管理（$O(N)$ 次元で実現）
単調Dequeで範囲内の最小dp値を $O(1)$ で取得

ヒント3: コード骨格

from collections import deque
import bisect

r_vals = sorted(set([0] + [r for l, r, a in intervals]))
dp = [INF] * len(r_vals)
dp[0] = 0
dq = deque([0])  # r_vals のインデックス

for l, r, a in intervals:
    cost = (r - l + 1)**2 + a
    hi = bisect.bisect_right(r_vals, l - 1) - 1
    while dq and dq[0] > hi: dq.popleft()
    if dq:
        ri = r_idx[r]
        val = dp[dq[0]] + cost
        if val < dp[ri]:
            dp[ri] = val
            while dq and dp[dq[-1]] >= dp[ri]: dq.pop()
            dq.append(ri)

模範解答 (Python)

import sys
from collections import deque
from bisect import bisect_right
input = sys.stdin.readline

def solve():
    N, M = map(int, input().split())
    intervals = []
    for _ in range(N):
        l, r, a = map(int, input().split())
        intervals.append((l, r, a))

    INF = float('inf')
    r_vals = sorted(set([0] + [r for l, r, a in intervals]))
    r_idx = {v: i for i, v in enumerate(r_vals)}
    sz = len(r_vals)

    dp = [INF] * sz
    dp[0] = 0

    dq = deque()
    dq.append(0)

    for l, r, a in intervals:
        cost = (r - l + 1) ** 2 + a
        hi = bisect_right(r_vals, l - 1) - 1

        while dq and dq[0] > hi:
            dq.popleft()

        if not dq:
            continue

        best = dp[dq[0]]
        if best == INF:
            continue

        ri = r_idx.get(r)
        if ri is None:
            continue

        val = best + cost
        if val < dp[ri]:
            dp[ri] = val
            while dq and dp[dq[-1]] >= dp[ri]:
                dq.pop()
            dq.append(ri)

    if M in r_idx:
        ans = dp[r_idx[M]]
    else:
        ans = INF

    print(ans if ans < INF else -1)

solve()

Step-by-Step 解説

Step 1: DP定義と遷移式

$dp[0] = 0$（未被覆の初期状態）。区間 $[l_i, r_i]$ を右端の昇順で処理し、$dp[r_i] = \min_{j \le l_i-1} dp[j] + c_i$ で更新。

Step 2: 座標圧縮

$M \le 10^9$ のため全座標を持てない。右端の値 $\{0, r_1, r_2, \ldots, r_N\}$ のみを圧縮してDPの次元とする。

Step 3: 単調Dequeの適用

操作	内容
フロントの削除	$j > l_i - 1$ のインデックスを削除（範囲外）
最小値取得	$dp[dq[0]]$ がフロントの最小値
バックへの追加	$dp[ri]$ より大きい末尾を削除してから追加（単調性維持）

Step 4: 計算量

操作	計算量
座標圧縮	$O(N \log N)$
DP処理	$O(N \log N)$（二分探索）
全体	$O(N \log N)$

よくあるミス

ミス	原因	正しい書き方
M が右端に存在しない	被覆できない場合を未考慮	r_idx.get(M) で -1 返却
dq更新の順序	dp[ri]更新前にdqを変更	dp[ri]を先に更新してからdq操作
コスト計算式ミス	$(r-l+1)^2$ の誤り	長さは r-l+1（両端を含む）

次のステップ

発展問題: コストが線形関数 $c_i = a_i \cdot r_i + b_i$ の場合のCHT適用（Li Chao Tree）。または区間の重複が許されないスケジューリング問題への応用。

自己評価

完全理解おおむね理解要復習