Aliens 優化

tags: Competitive Programming Note

本文已停止更新，新版請至 WiwiHo 的競程筆記

Aliens 優化是 DP 優化的一種，先看例題：AI-666 賺多少，雖然這題有 Greedy 的作法，但我們要用 Aliens 優化來做。

先想想看如果沒有交易次數的限制可以怎麼做，令

$d{p}_0[i]$ 是到第

$i$ 個時間點結束時，手上沒有商品的最大獲利，而

$d{p}_1[i]$ 是手上有商品的最大獲利，

$a[i]$ 是時間點

$i$ 時商品的價格，然後可以很簡單地得到轉移式：

$$\begin{array}{rl}d{p}_0[i]& =max(d{p}_0[i-1],d{p}_1[i-1]+a[i])\\ d{p}_1[i]& =max(d{p}_1[i-1],d{p}_0[i-1]-a[i])\end{array}$$ 答案就是

$d{p}_0[N]$，算這個的同時也可以得到最大獲利需要的最少交易次數是多少。用相似的作法再加上一個維度，就可以算在交易次數限制下的最大獲利了，不過那樣的時間複雜度是

$O(NK)$，所以我們不會這樣做。

令

$f(k)$ 是做恰

$k$ 次交易時的最大獲利，雖然我們不能很快地算出

$f(k)$，但我們可以用

$O(N)$ 的時間算出

$max\{f(k)\}$ 和得到極值發生的

$k$，也就是最大獲利和需要的交易次數。先知道這件事，待會會用到。

$f(k)$ 有一個重要的性質是，它是一個凹函數（concave function），凹函數的意思是這個函數的切線斜率也就是差分（我們都在整數上做事）非嚴格遞減，用直覺的方式說明一下就是如果

$f(k-1)-f(k-2)<f(k)-f(k-1)$，也就是

$f(k)$ 多做的那次獲利比

$f(k-1)$ 多做的那次多，那麼我乾脆把

$f(k-1)$ 多做的那次交易換成

$f(k)$ 多做的那次，所以多出來的獲利一定會越來越少。

那麼凹函數可以幹嘛呢？我們要做一件神奇的事情，就是對每次交易多收

$p$ 元的手續費，令得到的新函數是

$f^{\prime }(k)=f(k)-kp$，而

$f^{\prime }(k)$ 也會是凹函數，因為：

$$f^{\prime }(k)-f^{\prime }(k-1)=(f(k)-kp)-(f(k-1)-(k-1)p)=f(k)-f(k-1)-p$$ 所以就只是

$f(k)$ 的差分全部減去

$p$ 而已，差分遞減這件事不會改變。

要計算

$max\{f(k)-kp\}$ 和極值發生的

$k$ 很簡單，只要修改一下轉移式：

$$d{p}_1[i]=max(d{p}_1[i-1],d{p}_0[i-1]-a[i]-p)$$ 同樣可以

$O(N)$ 算出來。

接下來注意到一件事：對於一個凹函數，它的極值發生點就是第一個

$f^{\prime }(k+1)-f^{\prime }(k)\le 0$ 的

$k$，而「把差分全部減去

$p$」就會改變這個位置，然後我們又可以輕鬆算出來極值和它的位置，還有顯然

$p$ 越大，極值就會在越左邊的地方，因此我們可以二分搜

$p$（為了實作方便，我們讓這個

$p$ 是最小的那一個，它會等於

$f(k+1)-f(k)$，讓

$f^{\prime }(k+1)-f^{\prime }(k)$ 剛好變 0），讓極值發生在我們想要的

$K$，就可以得到

$f(K)-Kp$，把

$Kp$ 加回去就是答案了。（這題有一個要特別注意的地方是如果本來極值位置就

$\le K$，要直接輸出答案。）

示意圖，藍色是

$f^{\prime }(k)$，紅色是

$f^{\prime }(k+1)-f^{\prime }(k)$，金色是極值的位置：

有一個特殊狀況是，因為我們是找「最大獲益需要的最少交易次數」，也就是最左邊的極值位置，而在

$f(K)-f(K-1)=f(K+1)-f(K)$，也就是

$f(K-1),f(K),f(K+1)$ 等差時，

$K$ 永遠不會是差分第一個變成

$\le 0$ 的點，也就不會是最左邊的極值位置。在這個時候，如果直接二分搜的話，會得到一個

$t$ 滿足

$$p=f(t+1)-f(t)=f(t+2)-f(t+1)=...=f(K)-f(K-1)=f(K+1)-f(K)$$ 也就是

$t$ 到

$K$ 會是一條直線，且

$t$ 是整條等差的最左邊那個點，可以推得：

$$\begin{array}{rl}& f^{\prime }(t+1)-f^{\prime }(t)=...=f^{\prime }(K+1)-f^{\prime }(K)\\ =& f(t+1)-f(t)-p=...=f(K+1)-f(K)-p\\ =& p-p=0\end{array}$$ 也就是

$f^{\prime }(t)=f^{\prime }(t+1)=...=f^{\prime }(K)$，因此

$f^{\prime }(t)+Kp=f^{\prime }(K)+Kp$，直接加

$Kp$ 也會是好的，結論就是完全不用理會這個狀況。

至於二分搜的上下界呢？因為我們希望最後找到

$p=f(K+1)-f(K)$，所以這個數字一定要在二分搜的範圍裡，因此二分搜範圍就和差分的範圍一樣。如果不會算的話也可以隨便開一個很大的範圍，反正二分搜很快，TLE 再縮小就好。

時間複雜度是

$O(N\log C)$，比

$O(NK)$ 好多了。

總結

Aliens 優化就是用這種「移動極值」的想法，來把本來要多開一個維度的事用二分搜做掉。如果用互動題來講，會像是這樣：

有一個凹函數

$f(k)$，你不知道它長什麼樣子，但是你可以把一個數字

$p$ 丟進一台機器裡，它會告訴你最大的

$f(k)-kp$ 是多少，以及讓這個值最大的

$k$ 為何，求

$f(K)$。

除了凹函數可以用以外，凸函數（差分非嚴格遞增的函數）也可以用 Aliens 優化做，因為它和凹函數同樣有差分具單調性的特性，這樣的題目會變成是求最小值，而極值發生的位置變成第一個

$f(k+1)-f(k)\ge 0$ 的地方，還有

$f(k)-kp$ 要換成

$f(k)+kp$（這樣才不用改太多東西 (?)），就是想成它是一個凹函數倒過來就好了。

如果

$p$ 可能是負數，二分搜的時候注意除法會向零取整。

實作細節

實作就二分搜而已，但有一件特別重要的事情是

$p$ 是要找最小那一個，在這個時候我們一定會找到

$p=f(K+1)-f(K)$，剛剛我們都是以這件事為前提做事的，現在來仔細分析一下不這樣做會怎樣。

我們的主要目標是「找到

$p$ 使得

$f(k)-kp$ 的極值在

$K$」，在

$f(K)-f(K-1)\ne f(K+1)-f(K)$ 時，而這個

$p$ 的範圍可以是

$[f(K+1)-f(K),f(K)-f(K-1))$ 中的任何一個數，在這種時候無論我們找到的

$p$ 是多少，只要落在這個範圍就會是好的，因為極值一定在

$K$。

而當

$f(K)-f(K-1)=f(K+1)-f(K)$ 就會發生前面有提到的，

$K$ 不可能是極值位置的狀況發生，這個時候，如果你的二分搜長這樣：

while(l < r){
    int m = (l + r + 1) / 2;
    if(calc(m) >= K) l = m; // calc(p) = f(k)-kp 的最左邊極值位置
    else r = m - 1;
}

也就是你試圖去找到最大的好的

$p$，而不是最小的，這樣你其實會得到

$p=f(K+1)-f(K)-1$，因為一旦

$p\ge f(K+1)-f(K)$，極值位置就會跑到

$K$ 的左邊去，這樣子

$f^{\prime }(K+1)-f(K)$ 會是 1，且得到的極值位置會是整條等差最右邊那個點，跟我們剛剛想要的

$f^{\prime }(K+1)-f(K)=0$ 完全不一樣，直接加

$Kp$ 回去也會是錯的。

所以二分搜要長這樣才對：

while(l < r){
    int m = (l + r) / 2;
    if(calc(m) <= K) r = m;
    else l = m + 1;
}

其實也不是一定要這樣，如果你拿上面兩份程式碼各跑一次，會得到兩個

$p$，假設找最小版是

$p_1$、找最大版是

$p_2$，而得到的極值位置會在整條等差的最左和右邊，假設是

$v_1$ 和

$v_2$，你可以得到

$f(v_1)$ 和

$f(v_2)$，反正它們兩個之間等差且

$K$ 在中間，那就用它們算出

$f(K)$ 就好：

$$f(K)=f(v_1)+\frac{f(v_2)-f(v_1)}{v_2-v_1}\times (K-v_1)$$ 但是直接加

$Kp$ 的作法顯然輕鬆許多，所以就好好找最小的

$p$ 吧。