Convex Hull Trick - 알고리즘카

이 글은 시리즈의 일부입니다. 먼저 이전 글을 모두 읽기를 권장합니다.

$f$에 대한 원래 공식을 가져와 cost의 괄호를 풀어 봅시다:

$$ \begin{aligned} f[i, j] &= \min_{k < i} \{ f[k, j-1] + (x_{i-1}-x_k)^2 \} \\ &= \min_{k < i} \{ f[k, j-1] + x_{i-1}^2 - 2x_{i-1} x_k + x_k^2 \} \end{aligned} $$ $x_{i-1}^2$은 $k$에 의존하지 않으므로 밖으로 꺼낼 수 있다는 점에 주목하십시오. 그러면 최솟값 안에는 다음만 남습니다. $$ \underbrace{(f[k, j-1] + x_k^2)}_{a_k} + \underbrace{(-2 x_k)}_{b_k} \cdot x_{i-1} $$ 항들을 재배열하면, 원래 식을 다음과 같이 다시 쓸 수 있음을 얻습니다. $$ f[i, j] = \min_k \{ (a_k, b_k) \cdot (1, x_{i-1}) \} $$

여기서 «$\cdot$»는 내적을 의미합니다.

#알고리즘

$f[i, j]$에 대한 최적의 $k$를 찾고자 한다고 합시다. 이전 층에서 이미 계산된 관련 DP 값들을 모두 평면 위의 점 $(a_k, b_k)$로 나타내 봅시다.

그 가운데 스칼라곱이 최소인 점을 효율적으로 찾으려면 점들의 하부 포락선을 유지하고 그 위에서 이진 탐색으로 최적의 점을 찾으면 됩니다. 벡터 $(1, x_{i-1})$는 항상 위쪽을 “향하므로” 우리에게 필요한 것은 하부 포락선뿐입니다.

하부 포락선은 간단히 스택에 저장할 수 있습니다. 추가되는 점들이 $x$에 대해 정렬되어 있으므로 하부 포락선의 구성에는 선형 시간이 걸리고, 전체 알고리즘의 점근적 복잡도는 이진 탐색의 점근적 복잡도에 의해 결정되어 $O(n m \log n)$이 됩니다.

struct line {
    int k, b;
    line() {}
    line(int a, int _b) { k = a, b = _b; }
    int get(int x) { return k * x + b; }
};

vector<line> lines; // храним прямые нижней огибающей
vector<int> dots; // храним x-координаты точек нижней огибающей
//     ^ первое правило вещественных чисел
//      считаем, что в dots лежит округленная вниз x-координата

int cross(line a, line b) { // считаем точку пересечения
                            // считаем a.k > b.k
    int x = (b.b - a.b) / (a.k - b.k);
    if (b.b < a.b) x--; // боремся с округлением у отрицательных чисел
    return x;
}


void add(line cur) {
    while (lines.size() && lines.back().get(dots.back()) > cur.get(dots.back())) {
        lines.pop_back();
        dots.pop_back();
    }
    if (lines.empty())
        dots.push_back(-inf);
    else 
        dots.push_back(cross(lines.back(), cur));
    lines.push_back(cur);
}

int get(int x) {
    int pos = lower_bound(dots.begin(), dots.end(), x) - dots.begin() - 1;
    return lines[pos].get(x);
}

우리가 다루는 구체적인 문제의 경우, $opt[i, j] \leq opt[i][j+1]$, 즉 최적 지점이 항상 «더 오른쪽»에 있다는 사실을 떠올리면 알고리즘을 더 최적화할 수 있습니다. 이를 이용하면 이진 탐색 대신 두 포인터 기법을 적용할 수 있고, 그렇게 하여 해법을 $O(n m)$까지 최적화할 수 있습니다.