概要

Dequeを用いてConvex Hull Trickを行うアルゴリズム

蟻本[1]に載っている。

以下の条件を満たす場合、CHTを線形オーダーで解くことができる。

  1. 追加する直線の傾きが単調増加(減少)

  2. 計算する最小値(最大値)の座標\(x\)が単調増加(減少)

計算量

  • \(N\)本の直線追加: \(O(N)\)

  • \(Q\)個の座標における最小値: \(O(Q)\)

実装

from collections import deque
deq = deque()
def check(f1, f2, f3):
    return (f2[0] - f1[0]) * (f3[1] - f2[1]) >= (f2[1] - f1[1]) * (f3[0] - f2[0])
def f(f1, x):
    return f1[0]*x + f1[1]

# add f_i(x) = a*x + b
def add_line(a, b):
    f1 = (a, b)
    while len(deq) >= 2 and check(deq[-2], deq[-1], f1):
        deq.pop()
    deq.append(f1)

# min f_i(x)
def query(x):
    while len(deq) >= 2 and f(deq[0], x) >= f(deq[1], x):
        deq.popleft()
    return f(deq[0], x)

Verified

  • AtCoder: "Educational DP Contest / DP まとめコンテスト - Z問題: Frog 3": source (Python3, 747ms), source (PyPy3, 413ms)



1. プログラミングコンテストチャレンジブック [第2版] p.304