Alien DP をざっくり理解する

Alien DP という名前は Twitter でたまに見かけますが、その詳しい内容を調べようとしてもなかなか大変だったので備忘録もかねてここに書いておきます。

Alien DP は ABC で出題されており、その解説で詳しい説明がなされているのでネタバレをされてもよい方はそちらも参照すると良いでしょう。

数理的な詳しい解説は Monge グラフ上の $d$-辺最短路長を計算するアルゴリズム | Kyopro Encyclopedia of Algorithms になされているので、本記事では正当性の証明などは避けて直感的にどのようなアルゴリズムであるかを理解することを目標とします。

Alien DPで解ける問題

Alien DPは次のようなことができるアルゴリズムです。

$x = 0, 1, 2,\dots, N$ とする。 $f(x)$ が下に凸である。つまり任意の $x\le N-2$ に対して $f(x+1) - f(x) \ge f(x+2) - f(x+1)$ が成立するとする。もし任意の定数 $c$ に対して $\min_{x = 0, 1, 2,\dots, N}{(f(x) - cx)}$ が $\Theta(\alpha)$ で計算できるなら任意の $k = 0, 1, 2,\dots, N$ に対して $f(k)$ を $\Theta(\alpha\log max(f(x+1) - f(x)))$ で計算できる。

$f(k)$ より $\min_{x = 0, 1, 2,\dots, N}{(f(x) - cx)}$ を高速に計算できる場面がぱっと思いつかないかもしれません。例えば、長さ $N$ の配列に対し、そのうち $k$ 個の要素を使った最適化をするために $dp[i][j] = \{i番目までにj個の要素を使ったときの最適値\}$ とするようなdpをしたいがそのままでは $\Theta(N^2)$ で間に合わないときが考えられます。*1

アルゴリズム

$\min_{x = 0, 1, 2,\dots, N}{(f(x) - cx)}$ を求める操作は $y = f(x)$ のグラフと傾き $c$ の直線が接するときの接点を求める操作に対応します。これは傾き $c$ の直線の式を $y = cx + b$ とおいて、 $y = f(x)$ との交点をもつようにしながら $b$ を最小化していると考えるとよいです。