Day 033-Q1 | Kinetic Heap (CHT融合)

問題

$N$ 個の荷物があり、荷物 $i$ の時刻 $t$ における重さは $a_i \cdot t + b_i$。$Q$ 個のクエリ $t_k$（単調増加）について、その時刻における全荷物の重さの最小値を出力せよ。

入力形式

N Q
a_1 b_1
...
a_N b_N
t_1 t_2 ... t_Q

制約

$1 \le N \le 2 \times 10^5$

$1 \le Q \le 2 \times 10^5$

$-10^9 \le a_i \le 10^9$, $0 \le b_i \le 10^9$

$1 \le t_1 < \cdots < t_Q \le 10^9$

入出力例

入力例 1

出力例 1

ヒント (段階的開示)

ヒント1: 方向性

各重さは $t$ の一次関数。下凸包の最小値クエリ。クエリ単調増加なら単調 CHT。

ヒント2: アプローチ

傾き昇順にソート → スタックで下凸包構築 $O(N \log N)$。ポインタを右にしか動かさず $O(N+Q)$。

ヒント3: 誘導

lines.sort()  # 傾き昇順
hull = []
for line in lines:
    while len(hull) >= 2 and bad(hull[-2], hull[-1], line):
        hull.pop()
    hull.append(line)
ptr = 0
for t in queries:
    while ptr+1 < len(hull) and val(hull[ptr+1], t) <= val(hull[ptr], t):
        ptr += 1

模範解答 (Python)

import sys

def solve():
    data = sys.stdin.read().split()
    idx = 0
    N, Q = int(data[idx]), int(data[idx+1]); idx += 2
    lines = []
    for _ in range(N):
        a, b = int(data[idx]), int(data[idx+1]); idx += 2
        lines.append((a, b))
    queries = [int(data[idx+i]) for i in range(Q)]

    lines.sort()

    hull = []

    def bad(l1, l2, l3):
        return (l3[1] - l1[1]) * (l1[0] - l2[0]) <= (l2[1] - l1[1]) * (l1[0] - l3[0])

    for a, b in lines:
        while len(hull) >= 2 and bad(hull[-2], hull[-1], (a, b)):
            hull.pop()
        if hull and hull[-1][0] == a:
            if b < hull[-1][1]:
                hull.pop()
            else:
                continue
        hull.append((a, b))

    ptr = 0
    results = []
    for t in queries:
        while ptr + 1 < len(hull):
            v_cur = hull[ptr][0] * t + hull[ptr][1]
            v_nxt = hull[ptr+1][0] * t + hull[ptr+1][1]
            if v_nxt <= v_cur:
                ptr += 1
            else:
                break
        results.append(hull[ptr][0] * t + hull[ptr][1])

    sys.stdout.write('\n'.join(map(str, results)) + '\n')

solve()

Step-by-Step 解説

1直線の最小値問題に変換
$f_i(t) = a_i t + b_i$ について $\min_i f_i(t_k)$。

2下凸包の構築
傾き昇順ソート → スタックに追加しながら不要直線を pop。整数で交点判定: $(b_3 - b_1)(a_1 - a_2) \le (b_2 - b_1)(a_1 - a_3)$。

3単調クエリへの対応
クエリ単調増加なら凸包ポインタを右にのみ移動。全体で $O(N+Q)$。

計算量

前処理（ソート + 凸包）: $O(N \log N)$
クエリ処理: $O(N + Q)$
全体: $O((N + Q) \log N)$

よくあるミス

ミス	原因	正しい書き方
上凸包と下凸包の混同	最小/最大で符号が変わる	最小値は傾き昇順・下凸包
同一傾きの処理忘れ	`bad()` が破綻	同一傾きは切片最小を残す
整数オーバーフロー	$10^{18}$ 超	Python は多倍長で安全
非単調クエリに単調CHT	クエリが降順だとポインタが戻る	非単調なら Li Chao Tree

Day 033-Q1 — Kinetic Heap（動的優先度付きキュー・凸包トリック融合）

問題