Aliens DP の整理 - rogi52’s blog

陽には与えられない、下に凸な関数 $f \colon \mathbb{Z} \to \mathbb{R}$ があるとします。任意の $p \in \mathbb{R}$ に対して $g(p) = \min \limits _ {x \in \mathbb{Z}} \lbrack f(x) - px \rbrack$ が $O(T)$ 時間で計算できるとき、任意の $x ^ {\mathrm{target}} \in \mathbb{Z}$ に対して $f(x ^ { \mathrm{target} } )$ が $O(T \log P)$ 時間で計算できます。ただし、傾き $f(x+1) - f(x)$ が bound されていて、 $P = \max \limits _ {x \in \mathbb{Z}} \lbrack f(x+1) - f(x) \rbrack - \min \limits _ {x \in \mathbb{Z}} \lbrack f(x+1) - f(x) \rbrack$ とします。

アルゴリズム

$x ^ {\mathrm{target} } \in \mathop{ \mathrm{arg\,min} } \limits _ {x} \lbrack f(x) - p x \rbrack$ を満たす $p$ を見つけます。

方針として二分探索と三分探索の 2 つが考えられます。

(傾き) 二分探索

簡単のために $\mathop{ \mathrm{arg\,min} } \limits _ {x} \lbrack f(x) - px \rbrack$ は $1$ 元集合とします。 $g(p) = \min \limits _ {x} \lbrack f(x) - px \rbrack$ を求める操作は、 $y = f(x)$ と傾き $p$ の直線が接するときの接点の $y$ 座標を求める操作に対応しています。 $f$ が下に凸ですから、 $p \mapsto \mathop{ \mathrm{arg\,min} } \limits _ {x} \lbrack f(x) - px \rbrack$ は広義単調増加です。したがって二分探索ができます。

$x^* _ p = \mathop{ \mathrm{arg\,min} } \limits _ {x} \lbrack f(x) - px \rbrack$ を求めます。まず $g(p)$ を計算します。次に、十分小さい $\varepsilon \in \mathbb{R}$ について $g(p + \varepsilon)$ を計算します。このとき

$\begin{align*} \mathop{ \mathrm{arg\,min} } \limits _ {x} \lbrack f(x) - px \rbrack = \mathop{ \mathrm{arg\,min} } \limits _ {x} \lbrack f(x) - (p + \varepsilon ) x \rbrack = x ^ * _ p \end{align*}$

が成り立ちます。したがって

$g(p) - g(p + \varepsilon ) = \lbrack f(x ^ * _ p) - p x ^ * _ p \rbrack - \lbrack f(x ^ * _ p) - (p + \varepsilon ) x ^ * _ p \rbrack = \varepsilon x ^ * _ p$

より $x ^ * _ p$ を求めることができます。あとは $x ^ * _ p$ と $x ^ { \mathrm{target} }$ の大小で分岐すれば良いです。 $g(p)$ を計算する際に、同時に $x ^ * _ p$ が計算できるならばこの部分は簡略化できます。

三分探索

任意の $p$ について次が成り立ちます。

$\min \limits _ {x} \lbrack f(x) - px \rbrack \leq f( x ^ {\mathrm{target}} ) - p x ^ {\mathrm{target}}$

移項して $p$ について $\max$ をとると

$f(x ^ { \mathrm{target} }) = \max \limits _ {p } \left \lbrack \min \limits _ {x } \lbrack f(x) - px \rbrack + p x ^ {\mathrm{target}} \right \rbrack$

が成り立ちます。 $p \mapsto g(p) + p x ^ {\mathrm{target}}$ は上に凸ですから、三分探索ができます。

なお次のように式変形すると、制約 $x = x ^ { \mathrm{target} }$ のラグランジュ緩和とのつながりがわかりやすくなります。ラグランジュ緩和と Aliens DP の対応については [1] に示されています。

$f(x ^ { \mathrm{target} }) = \max \limits _ {p } \left \lbrack \min \limits _ {x } \lbrack f(x) + p \left(x ^ { \mathrm{target} } - x \right) \rbrack \right \rbrack$

整数値の場合

$f(x) - px$ の値が等しくなる tie-breaking について注意を払う必要があります。

対処法については [2] が非常に参考になります。

ペナルティ回数の管理は、 $g(p)$ の計算と同時に $x ^ * _ p$ を求めることを指しています。三分探索については同様です。傾き二分探索については $\varepsilon = 0.5$ に注目します。

$f(x ^ { \mathrm{target} })$ が与えられる場合

はじめ考えたのは $x ^ { \mathrm{target} }$ が与えられたとき $f(x ^ { \mathrm{target} })$ を求める問題です。

逆に $f(x ^ { \mathrm{target} } )$ が与えられたとき $x ^ { \mathrm{target} }$ を求める問題も考えられます。

本記事の手法を用いて二分探索することもできますが、[2] で紹介されているように適切に $f$ を平行移動した後 $- g(p) / p$ について三分探索することで $\log$ を一つ落とすことができます。

アルゴリズムの適用

[3] は Aliens DP の名前の由来となった問題です。この問題のように $f(x) :=$ $x$ 個使ったときの何らかの最適値、という関数について Aliens DP が適用できる可能性があります。これは次の可能性からです。

を直接求めることが難しい
- 最適値を求める際に、これまでに何個使ったかを覚えておく必要があります
- 例えば $n$ 個の要素について $\mathrm{dp} _ {i, j} := i$ 番目まで見て $j$ 個使ったときの最適値、とすると $\Omega (n ^ 2)$ 時間です
を求めることが易しい
- 添字に持つ必要があった個数の情報が、 $p$ を用いて DP の値に取り込まれます
- 個数の情報を持たない場合、 $o(n ^ 2)$ 時間で計算できる可能性があります