Alien DP についてのメモ

Alien DPの自分なりの理解をメモ。

アルゴリズムの説明

$M = ( M_0, M_1, ..., M_n )$ を広義で上に凸であることがわかっている未知の数列とする。

与えられた $k$ に対して $M_k$ を求めることを目指す。

$a_i = M_{i+1}-M_i$ とおくと、 $M$ が広義で上に凸であることから $a_i$ は広義単調減少である。

この時関数 $f_i, g$ を $f_i(x) = -ix+M_i$ 、 $g(x) = \max\limits_{0 \leq j \leq n} f_j(x)$ で定義すると以下の補題が成り立つ。

補題

$x \in [a_i : a_{i-1} ]$ の時、 $g(x) = f_i(x)$ である。

(ただし便宜上 $a_{-1} = \infty, a_n = -\infty$ とする)

証明

$a_i \leq x \leq a_{i-1}$ として、 $0 \leq j \leq n$ に対し $f_j(x) \leq f_i(x)$ を示す。

$j \geq i$ の時と $j \leq i$ の時で場合分けする。

$j \geq i$ の時、

$$ \begin{aligned} f_i(x)-f_j(x) &= -ix+M_i+jx-M_j \\ &= (j-i)x-(M_j-M_i) \\ &= (j-i)x-(a_i+a_{i+1}+\ldots+a_{j-1}) \\ &\geq (j-i)x-(j-i)a_i \\ &= (j-i)(x-a_i) \\ &\geq 0 \end{aligned} $$

である。 $j \leq i$ の場合も同様。

(証明終)

上の補題から、全ての $0 \leq i \leq n$ に対して $g(x) = f_i(x)$ を満たす $x$ が存在することがわかる。

また、そのような $x$ が取りうる範囲 $[a_i : a_{i-1} ]$ は $i$ が増加するごとに負の方向に移動する。

したがって $0 \leq k \leq n$ が与えられた時、 $g(x) = f_k(x) = -kx+M_k$ となるような $x$ を求めれば、 $M_k = g(x)+kx$ で $M_k$ を求めることができる。

下の画像は $M= ( 0, 10, 14, 14, 9 )$ の時の $f_i(x), g(x)$ のイメージ。

補足

$x$ が与えられた時に $g(x)$ がそれなりの速度( $O(N)$ とか)で求められる必要がある。
競プロでは $M_k$ を「それぞれにスコアが与えられている何かの集合の中から(条件を満たしつつ) $k$ 個選んだ時のスコアの合計の最大値」のように定義した場合、すなわち
$M_k = \max\limits_{S \in {\cal S}, |S|=k} \sum\limits_{t \in S} c_t$
のような形の時、

$\begin{aligned} g(x) &= \max\limits_{0 \leq k \leq n} \left( -kx + \max\limits_{S \in {\cal S}, |S|=k} \sum\limits_{t \in S} c_t \right) \\ &= \max\limits_{0 \leq k \leq n} \max\limits_{S \in {\cal S}, |S|=k} \sum\limits_{t \in S} (c_t-x) \\ &= \max\limits_{S \in {\cal S}} \sum\limits_{t \in S} (c_t-x) \end{aligned}$

と変形でき、DPで $g(x)$ の値と、 $f_i(x)=g(x)$ となる $i$ の値が簡単に求まることがある。

上の議論より、 ${M_i}$ が全て整数ならば $g(x) = f_k(x) = -kx+M_k$ となるような整数 $x$ が存在することがわかる。
また、そのような $x$ を二分探索する範囲は $[a_{n-1} : a_0 ]$ を含むように取れば良い。*1
$x_0 = a_l = a_{l+1} = \ldots = a_{r-1}$ の場合、すなわち $M$ の傾きが $[l:r]$ で単調な場合、全ての $i \in [l:r]$ に対して $f_i(x)=g(x)$ となる。
後述の問題例のように「 $M_k \leq X$ を満たす最小の $k$ を求める」ような場合に注意が必要となる。
下に凸な場合は $f_i(x) = ix+M_i$ 、 $g(x) = \min\limits_{0 \leq j \leq n} f_j(x)$ とおく。