이산 라그랑주 방법

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

마지막 최적화로, 라그랑주 승수법에서 영감을 받은 방법을 살펴보겠습니다. 이 방법은 올림피아드 분야에서 「람다 최적화」라고도 불립니다.

#문제의 변형

원래 문제를 약간 변형한 버전을 살펴봅시다. 같은 점들을 덮어야 하지만, 이제는 선분 개수에 엄격한 제한이 없고, 대신 추가 선분을 하나 사용할 때마다 어떤 상수 $\lambda$만큼 벌점을 받는다고 합시다.

그러면 최적화하려는 함수 $g$를 $f$를 통해 다음과 같이 나타낼 수 있습니다:

이 DP는 $O(n)$에 계산할 수 있습니다. 바로 이전 글인 Convex Hull Trick에서 정확히 이 작업을 했습니다.

#아이디어

관찰 1. 어떤 $\lambda$에 대해 $g_i$의 최적해에서 정확히 $k$개의 구간을 사용했다면, 그 해는 $f[i, k]$에 대해서도 최적입니다.

관찰 2. $\lambda$를 줄이면 $g_i$에 대한 최적의 구간 개수는 증가합니다.

최적화의 핵심 아이디어는 다음과 같습니다. $\lambda$에 대해 이진 탐색을 수행하고, 그 내부에서 주어진 $\lambda$에 대한 $g_i$의 최적해를 구합니다. 최적의 $k^\star$가 $k$보다 크게 나왔다면 다음 $\lambda$는 더 작아야 하며, 그렇지 않은 경우에는 그 반대입니다. $k^\star$가 $k$와 일치하면, 얻어진 해의 벌점을 제외한 순수 비용을 출력하기만 하면 됩니다.

따라서 CHT를 위한 점의 정렬을 이진 탐색 내부가 아니라 미리 해 두면, 문제를 $O(n \log n + n \log m)$에 풀 수 있습니다.

#구현

pair<ll, int> dp[maxn]; // dp[i] - (ответ, число отрезков)

void init() {
    for (int i = 0; i < maxn; i++) {
        dp[i] = make_pair(inf, 0);
    }
}

pair<ll, int> check(ll x) { // это можно соптимизировать
    init();
    dp[0] = make_pair(0ll, 0); // 1-индексация
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < i; j++) {
            dp[i] = min(dp[i], {dp[j].first + cost[j + 1][i] + x, dp[j].second + 1});
        }
    }
    return dp[n];
}

ll solve() {
    ll l = -1e14; // границы надо подбирать очень аккуратно!
    ll r = 1;
    while (l + 1 < r) {
        ll mid = (l + r) / 2;
        pair<ll, int> x = check(mid);
        if (x.second >= k)
            l = mid;
        else
            r = mid;
    }
    pair<ll, int> result = check(l);
    return result.first - l * return.second; // вычитаем штрафы
}

저자는 구현의 품질에 대해 사과드리며, 독자 여러분께서 이를 다시 작성하여 커밋해 주시기를 바랍니다.

#해의 존재성

우리는 한 가지 미묘한 점을 건너뛰었습니다. 애초에 최적의 $k^\star = k$가 되도록 하는 $\lambda$가 왜 존재하는 것입니까?

일반적인 경우 함수 $k^\star(\lambda)$가 이 값을 「건너뛰는」 일이 있을 수 있으며, 이는 실제로 문제가 됩니다. 단조성만으로는 객체 개수에 제약이 있는 임의의 문제를 이와 같은 방식으로 풀기에 충분하지 않습니다.

하지만 우리 문제에서는 다음 사실을 알 수 있습니다. 함수 $f[i, j]$는 두 번째 인자에 대해 비엄격하게 오목(위로 볼록)합니다. 즉,

다시 말해, 다음 구간을 하나씩 추가할 때마다 얻는 추가 «이득»은 증가하지 않습니다.

이제 수정된 DP의 식을

점 $(f[i, k], k)$와 벡터 $(1, \lambda)$의 스칼라곱을 최소화하는 것으로 볼 수 있습니다.

점 $(f[i, k], k)$의 위쪽 포락선은 볼록하므로, 각 점마다 그 점에 닿는 $\lambda$가 존재하며, 따라서 $k^\star = k$인 $\lambda$를 반드시 찾을 수 있습니다.