Aliens 優化

Previous四邊形優化 NextSlope Trick

Last updated 3 years ago

Was this helpful?

Aliens 優化

前言

Aliens 優化是從 IOI 2016 Aliens 來的一個技巧，而大陸其實在 2012 年就已經發明這個演算法了，那邊叫做 wqs二分，有興趣的可以看一下原始論文：

接下來的內容會使用到裡面的例題，而我會用我自己的理解來說明 Aliens 優化。

概述

Aliens 優化是用來解決 K-約束問題的一種演算法。什麼叫 K-約束問題呢？

我們會遇到像這樣的問題：給定 $n$ 個物品，規定以某種方式選擇若干個物品，而選擇物品的不同會有不同代價，規定必須選 $k$ 個物品的前提下最大/小化花費。舉個簡單的例子：給你一個長度為 $n$ 的序列，叫你恰好劃分成 $k$ 段，最大/小化價值；諸如此類的問題，就叫做 $k$ 約束問題。

上面這類的 DP 問題的複雜度通常會至少是 $O(NK)$ 的，因為需要 $O(NK)$ 的空間複雜度。(令 $dp(i,j)$ 代表前 $i$ 個物品選 $j$ 個之類的)。而 Aliens 優化可以將這個複雜度優化到 $O(NlogC)$ ，其中 $C$ 即二分值域，視題目而定。

而 Aliens 優化的使用上有一個先備條件：

令 $f(x)$ 代表選恰好 $x$ 個物品的最小價值， $f$ 是一個凸性函數。也就是滿足差分遞減/增 ( $f(x+1)-f(x)\leq (\geq) f(x)-f(x-1)$ )，的函數。

如果滿足上面條件的話就可以使用 Aliens 優化。而這個 trick 雖然放在 DP 優化，但事實上並不是只有 DP 才可以使用。

上面的論文裡面附了兩個很好的例子，一題是黑白生成樹、另一題是APIO Commando那題的改編版。接下來我們用這兩個例子來介紹 Aliens 優化要怎麼使用。讓我們先來看黑白生成樹這題：

黑白生成樹

給你一張 $n$ 點 $m$ 邊的無向帶邊權連通圖，每條邊會是黑色或白色，請求出一個恰有 $k$ 條白色邊的最小生成樹的權值和。 $1\leq n\leq 5\cdot 10^4,1\leq m\leq10^5,1\leq v_i\leq 100$

一看到這題可能會想要先 Greedy 選完白邊之後再選黑邊。但很可惜這是錯的。如果先選白邊的話可能會影響到樹的連通性，導致一些比較優的黑邊不能被選到。

而透過觀察可以發現，這題是一個 $k$ 約束問題，那麼我們可以試著用看看 Aliens。

令 $f(x)$ 代表恰選 $x$ 條白邊的最小生成樹權值和。 $f(x)$ 顯然是不能直接求出來的，但是我們可以觀察感覺可以發現 $f$ 是一個下凸函數。

在上面這張圖中， $x=4$ 的值是最小的，也就是說原圖的最小生成樹會有恰好 $4$ 條白邊。這時候如我我們想要求其他的點 $f(m)$ 呢？我們知道 $f(m)$ 是沒有辦法被快速求出來的，但最低點可以用 Kruskal 快速算出來。那如果，我們透過某些變換讓 $x=m$ 變成最低點呢？

由於 $f$ 是下凸的，所以如果我們能找到一條在 $x=m$ 的切線的話(這裡 $m=3$ )：

也就是說，如果我們求出在 $x=m$ 的一條切線，那麼把 $x=m$ 帶進去就會是我們的 $f(m)$ 。所以我們就把問題轉換成了找切線這個動作。

如果我們隨機選一條斜率為 $k$ 的切線去切，這條直線不一定會切在 $m$ 上。但是因為 $f$ 是一個下凸函數，所以斜率越大會切到的點越大，也就是斜率單調。所以如果我們知道斜率為 $k$ 的直線會切在哪裡，我們就可以調整直線斜率讓他最終切到 $m$ 。而這個過程也就是二分搜。

所以我們現在變成要知道的是一條斜率為 $k$ 的直線會切在哪裡。

假設我們已經知道 $k$ 了，令一條斜率為 $k$ 的直線 $y=kx+b$ 。這條直線與 $f$ 的交點就會是\left\{ \begin{array}\{ y=f(x)\\ y=kx+b \end{array} \right.，整理一下就可以變成 $b=f(x)-kx$ 。

而透過觀察發現，切線一定會落在 $b$ 最小的地方，也就是 $f(x)-kx$ 最小的地方。令 $g(x)=f(x)-kx$ ，其中 $g(x)$ 就代表著每多選一條白邊需要多付 $k$ 的代價下所求得的最小生成樹的最小權值(因為選 $x$ 條要多付 $kx$ )。

那麼我們就把原圖的所有白邊邊權加上 $k$ 再跑一次 Kruskal 就可以得到 $g(x)$ 了！至此再結合上面所述的二分搜就可以以 $O(NlogNlogC)$ 的複雜度解掉這題了。

雖然我們看起來已經做完了，這邊還有一些細節要注意：可能會有某些點是沒辦法被整數斜率的直線切到的。舉個例子：令 $m$ 是要切的點，斜率 $k$ 的線切到的是 $m-1$ 而 $k+1$ 切到的是 $m+1$ ，此時 $m$ 就不能被整數切到。這時候就可以使用 小數二分。但是小數二分的效率並不高，在某些題目可能會 TLE。事實上很多時候可以透過題目性質來避免掉小數二分。例如這題就是一個例子。如果出現了上述的這種情形，那就代表一定存在某條黑邊的邊權=某條白邊的邊權。這時候在做最小生成樹的時候就只要優先選擇白邊就可以了。證明留給讀者自行思考。下面參考資料也有。

黑白生成樹部分程式碼

#define pii pair<int, int>
struct E {
    int a, b, v, c;
} e[maxn], ae[maxn];
int pa[maxn], sz[maxn];
void init_dsu(int n) { for(int i = 1; i <= n; i ++) pa[i] = i, sz[i] = 1; }
int get(int x) { return pa[x] == x? x : pa[x] = get(pa[x]); }
void uni(int a, int b) {
    a = get(a), b = get(b);
    if(a == b) return;
    if(sz[a] > sz[b]) swap(a, b);
    sz[b] += sz[a];
    pa[a] = b;
}
pii kruskal(int n, int m) {
    init_dsu(n);
    sort(e + 1, e + m + 1, [](E a, E b) {
        if(a.v == b.v) return a.c < b.c;
        return a.v < b.v;
    });
    int ret = 0, cnt = 0, val = 0;
    for(int i = 1; i <= m; i ++) {
        int a = get(e[i].a), b = get(e[i].b);
        if(a == b) continue;
        uni(a, b);
        cnt ++;
        if(e[i].c == 0) ret ++;
        val += e[i].v;
    }
    return make_pair(ret, val);
}

int n, m, tar;

void solve() {
    scanf("%d%d%d", &n, &m, &tar);
    for(int i = 1; i <= m; i ++) {
        int a, b, c, v;
        scanf("%d%d%d%d", &a, &b, &v, &c);
        a ++, b ++;
        ae[i] = {a, b, v, c};
    }
    int l = -100, r = 100,  tt = 10, ans = 1e18;
    while(l <= r) {
        int mid = (l + r) >> 1;
        for(int i = 1; i <= m; i ++) {
            e[i] = ae[i];
            if(e[i].c == 0) e[i].v -= mid;
        }
        pii tp = kruskal(n, m);
        int t = tp.f, v = tp.s;
        if(t < tar) l = mid + 1;
        else {
            r = mid - 1;
            ans = v + mid * tar;
        }
    }
    printf("%d\n", ans);
}

PS. 這題還可以做得更快，先把白邊跟黑邊分開 sort 。之後 Kruskal 要排序的時候用雙指針排序即可。複雜度少一個log。

上面介紹了 Aliens 優化的用法，下面這邊來一題套用在 DP 上的用法。

APIO 2010 Commando 魔改題

給你一個長度為 $N$ 的正整數列 $x_1,...x_n$ 以及一個二次方程 $f(x)=x^2$ 。你可以將這個數列分成連續的很多塊，而該分法的價值就是每塊的總和帶入 $f$ 之後的函數值的總和。求最多分成 $K$ 塊可以獲得的最大價值為何。 $N\leq 10^5$

現在多了一個最多 $K$ 塊的限制，但顯然選少於 $K$ 塊是不優的。所以我們就把他當成 $k$ 約束問題來做就好了。

容易推出一個暴力的DP式： $dp(i,j)$ 代表前 $i$ 個分成 $j$ 塊的答案。

$dp(i,j)=\min\limits_{t<i}\{dp[t][j-1]+(sum(i)-sum(t))^2\}$

一樣，透過觀察打表可以發現 $dp(i)$ 是一個凸的函數，所以我們可以考慮使用Aliens。使用 Aliens 的話也就是每多選一塊需要多花 $k$ 的價值，所以 DP 式變成：

$dp(i)$ 代表前 $i$ 個的答案， $dp(i)=\min\limits_{j<i}\{dp(j)+(sum(i)-sum(j))^2\}+k$

於是這題就變成 Commando 那題 $A=1,B=0$ 的Case了， $O(N)$ 斜率優化解決！總複雜度： $O(NlogC)$ 。

總結

使用 Aliens Trick 的時機：K約束問題+凸性函數
如何判斷是否為凸性函數？
1. 寫一個暴力作法打表看有沒有差分遞減/增
2. 小心假設、大膽猜測、不用證明！
3. 通常證明都很不可愛，打表比較實際
檢查一下題目需不需要小數二分，或是可以靠題目性質轉成整數二分

題目

參考文獻