Aliens 트릭

문제 형태

"정확히 \(k\)개"라는 개수 제약이 붙은 최적화 DP를 생각하자. 예: 배열을 정확히 \(k\)개 구간 으로 나눌 때 비용 최소화, 또는 정확히 \(k\)개의 작업을 선택. 개수를 상태에 넣으면 \(dp[i][j]\) 처럼 차원이 하나 늘어 \(O(nk)\) 이상이 든다. Aliens 트릭(WQS 이분 탐색, 라그랑주 완화)은 이 제약을 벌점(penalty) 으로 바꿔 차원을 없앤다.

라그랑주 완화

"정확히 \(k\)개를 골랐을 때의 최적값"을 \(g(k)\) 라 하자. 각 선택(구간 하나, 작업 하나)에 벌점 \(\lambda\) 를 부과하면, 제약 없는 DP

$$ h(\lambda) = \min_{\text{선택 개수 } c}\big( g(c) + \lambda\, c \big) $$

를 빠르게 풀 수 있다(개수 차원이 사라짐). 이때 최적해가 사용한 개수 \(c^*(\lambda)\) 는 \(\lambda\) 가 커질수록 단조 감소한다(벌점이 세지면 적게 고른다). 따라서 \(c^*(\lambda)=k\) 가 되도록 \(\lambda\) 를 이분 탐색 하면 된다. 답은

$$ g(k) = h(\lambda^*) - \lambda^* k. $$

볼록성 조건

이 방법이 옳으려면 \(g(k)\) 가 \(k\) 에 대해 볼록(또는 오목) 해야 한다. 볼록하면 \(g(k)+\lambda k\) 의 기울기 부호로 \(k\) 를 이분할 수 있다. 볼록성은 보통 "구간을 하나 더 쪼갤 때 이득이 체감한다"는 문제 구조에서 나온다. 증명이 어렵다면 작은 입력으로 \(g(k)\) 의 차분 \(g(k+1)-g(k)\) 가 단조인지 확인한다.

동점(tie) 처리

\(\lambda\) 가 정수 격자에 걸리면 최적 개수가 한 값이 아니라 구간 \([c_{lo}, c_{hi}]\) 이 될 수 있다. 이때 \(k\) 가 그 구간에 들면 답을 복원할 수 있다. 구현에서 "개수가 같으면 더 많은(또는 적은) 개수를 선호" 하도록 타이브레이크를 두어 \(c^*\) 의 단조 경계를 만든다.

복잡도

\(\lambda\) 이분이 \(O(\log(\text{값 범위}))\), 각 평가가 무제약 DP 비용 \(T\) 이므로 전체 \(O(T\log V)\). 개수 차원 \(k\) 가 통째로 빠지는 것이 이득이다.

골격: "정확히 k구간 분할 최소비용"

각 구간을 만들 때 벌점 \(\lambda\) 를 더하고, 그 상태에서 무제약 최소비용 DP를 푼 뒤 사용한 구간 수를 함께 추적한다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18;

int n, K;
ll segCost(int l, int r);   // 구간 [l, r] 비용 (보통 누적합/볼록 비용)

// 벌점 lambda 하에서 (최소비용, 사용 구간 수) 반환. 구간 수는 타이에서 최대화.
pair<ll,int> solve(ll lambda) {
    vector<ll> dp(n + 1, INF);
    vector<int> cnt(n + 1, 0);
    dp[0] = 0;
    for (int j = 1; j <= n; j++)
        for (int i = 0; i < j; i++) {      // 실전에선 CHT/DnC로 가속
            ll val = dp[i] + segCost(i, j - 1) + lambda;
            if (val < dp[j] || (val == dp[j] && cnt[i] + 1 > cnt[j])) {
                dp[j] = val; cnt[j] = cnt[i] + 1;
            }
        }
    return {dp[n], cnt[n]};
}

ll aliens() {
    ll lo = 0, hi = 1e12, lam = 0;    // 비용/벌점 범위에 맞게 조정
    // 사용 구간 수가 K 이하가 되는 최소 lambda를 찾는다 (g(k) 오목 가정)
    while (lo <= hi) {
        ll mid = (lo + hi) / 2;
        if (solve(mid).second <= K) { lam = mid; hi = mid - 1; }
        else lo = mid + 1;
    }
    auto [cost, used] = solve(lam);
    return cost - lam * (ll)K;        // g(K) = h(lambda) - lambda*K
}

자주 하는 실수

• 볼록/오목 방향. 최소화 문제에서 \(g(k)\) 가 볼록이면 벌점 부호와 이분 방향을 거기에 맞춘다. 방향을 뒤집으면 엉뚱한 \(\lambda\) 로 수렴한다.
• 타이브레이크 누락. 동점에서 개수를 최대(또는 최소)로 고정하지 않으면 \(c^*(\lambda)\) 가 들쭉날쭉해 \(k\) 를 못 맞춘다.
• 정수 격자 함정. 답이 격자에 걸려 정확히 \(k\) 가 안 나올 때가 있다. 타이브레이크로 \(c^* \le k \le c^{**}\) 를 보장하고 복원한다.
• 벌점 범위. \(\lambda\) 상한을 최대 단일 구간 비용 차분보다 크게 잡는다.

응용

가속

내부 무제약 DP가 직선/볼록 비용이면 CHT나 분할 정복 최적화로 한 번의 solve 를 \(O(n\log n)\) 이하로 낮출 수 있다. 그러면 전체 \(O(n\log n\log V)\) 가 된다.