Aliens DP における二分探索の色々

とにかく使いたい人向け

スコアとペナルティがどちらも整数とする。 *1

ペナルティを $p$ にしたときの最適値を $g(p)$ と置く。

事実 $1$

ペナルティが $p$ の時の最適解がペナルティを受ける回数としてあり得るものは、区間 $\lbrack l _ p , r _ p \rbrack$ になっている。

事実 $2$

最小化 (ペナルティの度にスコアに $+ p$ ) なら、 $r _ {p + 1} = l _ p = g(p + 1) - g(p)$ である。

最大化 (ペナルティの度にスコアに $- p$ ) なら、 $r _ {p + 1} = l _ p = g(p) - g(p + 1)$ である。

使い方

$g(p)$ の計算の際にペナルティ回数の復元は不要で、 $g(p + 1) - g(p)$ (最大化なら逆) を返せばいい。

詳しめの解説

概要

Aliens DP などで二部探索をするときに用いる複数の手法を紹介する。

手法	利点	欠点
ペナルティ回数の管理	分かりやすい。ペナルティ回数を求める際に計算時間がほとんど増えない問題では最速。	ペナルティ回数の管理が面倒。tie-breaking に気を使わないと壊れる。
傾き二分探索	回数の管理が不要な中では最も分かりやすく、三分探索より速い。	最速ではない。
三分探索	凸じゃないケースで誤魔化せる可能性が傾き二分探索より高いかもしれない。	傾き二分探索のほぼ下位互換。
黄金分割探索	回数の管理で計算時間が嵩む場合最速。	ほぼライブラリ化前提、その場で書くのは苦しい。

問題設定

下に凸な関数 $f \colon \mathbb{Z} \to \mathbb{Z} \cup \lbrace + \infty \rbrace, ~ f \neq + \infty$ があり、 $g \colon \mathbb{Z} \to \mathbb{Z} \cup \lbrace - \infty \rbrace, ~ p \mapsto \inf \limits _ x \left ( f(x) - px \right )$ と定義する *2 。 $g(p)$ は、 $y = f (x)$ のグラフに傾き $p$ の接線を引いた際の $y$ 切片の値と解釈することもできる。我々の目標は、任意の $p \in \mathbb{Z}$ に対して $g \left ( p \right )$ が高速に計算できるとき、与えられた $\tilde x \in \mathbb{Z}$ に対する $f \left ( \tilde x \right )$ を計算することである。

ペナルティ回数の管理

$\inf \limits _ x \left ( f(x) - px \right )$ を達成する最小の $x$ を $x ^ {\ast} _ p$ とする。 $g \left ( p \right )$ の評価の際に $x ^ {\ast} _ p$ を同時に計算できる場合を考える。

$x ^ {\ast} _ p$ は $p$ に対して単調増加であるから、二分探索を用いて $x ^ {\ast} _ {\tilde p} \leq \tilde x \lt x ^ {\ast} _ {\tilde p + 1}$ を満たす $\tilde p$ を発見できる。すると $\tilde x \in \mathop{ \mathrm{arg\,min} } \limits _ x \left ( f(x) - \tilde p x \right )$ であるから、 $g \left ( \tilde p \right ) = f \left ( \tilde x \right ) - \tilde p \tilde x$ から $f \left ( \tilde x \right )$ の値が分かる。

$x ^ {\ast} _ p$ の定義を $\inf$ を達成する最大の $x$ とした場合も、 $x ^ {\ast} _ {\tilde p - 1} \lt \tilde x \leq x ^ {\ast} _ {\tilde p}$ を満たす $\tilde p$ を発見すれば同様である。一方で、 $\min$ を達成する $x$ を何か $1$ つ計算できるとした場合、この方法では $f \left ( \tilde x \right )$ を特定できない *3 。

傾き二分探索

$\mathop{ \mathrm{arg\,min} } \limits _ x \left ( f(x) - p x \right )$ と $\mathop{ \mathrm{arg\,min} } \limits _ x \left ( f(x) - \left ( p + 1 \right ) x \right )$ の共通部分は $1$ 元集合であり、 $\mathop{ \mathrm{arg\,min} } \limits _ x \left ( f(x) - \left ( p + 0.5 \right ) x \right )$ と一致する。証明は容易なので省略する。

上記の事実から、 $\left \lbrace x ^ {\ast} _ {p + 0.5} \right \rbrace = \mathop{ \mathrm{arg\,min} } \limits _ x \left ( f(x) - \left ( p + 0.5 \right ) x \right )$ と定義すると以下の式が成り立つ。

\begin{align} g ( p ) &= f \left ( x ^ {\ast} _ {p + 0.5} \right ) - p x ^ {\ast} _ {p + 0.5} \cr g ( p + 1 ) &= f \left ( x ^ {\ast} _ {p + 0.5} \right ) - \left ( p + 1 \right ) x ^ {\ast} _ {p + 0.5} \end{align}

ここから $x ^ {\ast} _ {p + 0.5} = g ( p ) - g ( p + 1 )$ が分かるため、 $g$ の評価ができるだけで $x ^ {\ast} _ {p + 0.5}$ を得ることができる。後は二分探索を用いて $x ^ {\ast} _ {\tilde p - 0.5} \leq \tilde x \leq x ^ {\ast} _ {\tilde p + 0.5}$ を満たす $\tilde p$ を発見すれば、ペナルティ回数の管理の節と同様である。

本節の内容は $\mathop{ \mathrm{arg\,min} } \limits _ x \left ( f(x) - p x \right ) = \left \lbrack x ^ {\ast} _ {p - 0.5} , x ^ {\ast} _ {p + 0.5} \right \rbrack$ を意識すると理解しやすいかも知れない。

また、ペナルティ回数の管理を用いて $x ^ {\ast} _ {p + 0.5}$ を直接求めることで本節の内容を実行しても良い。その場合、 $\mathop{ \mathrm{arg\,min} } \limits _ x \left ( f(x) - \left ( p + 0.5 \right ) x \right ) = \mathop{ \mathrm{arg\,min} } \limits _ x \left ( 2 f(x) - \left ( 2 p + 1 \right ) x \right )$ を用いると整数の範囲で計算できる。

三分探索

$g$ の定義より、任意の $p$ について $g(p) \leq f \left ( \tilde x \right ) - p \tilde x$ である。これを移行して $f \left ( \tilde x \right ) \geq g(p) + \tilde x p$ としたのち両辺を $p$ についての $\sup$ をとると、 $f \left ( \tilde x \right ) \geq \sup \limits _ p \left ( g(p) + \tilde x p \right )$ を得る。 $f \left ( \tilde x \right ) \lt +\infty$ として、 $f$ の凸性から $g(p) = f \left ( \tilde x \right ) - p \tilde x$ を満たす $p$ が存在するため前述の式は等号で成立し、

\begin{align} f \left ( \tilde x \right ) = \sup \limits _ p \left ( g(p) + \tilde x p \right ) \end{align}

である。 $g$ は線形関数の $\inf$ で定義されるから上に凸であり、従って $p \mapsto g (p) + \tilde x p$ も上に凸であるから、三分探索を用いて最大化すればよい。

傾き二分探索の節の内容は、 $p \mapsto g (p) + \tilde x p$ の最大化を傾きの二分探索で行っているのと本質的に同じである。よって、傾き二分探索の節の内容を押し進めて三分探索に行き着くことも可能である。

黄金分割探索

三分探索の節の内容をそのまま黄金分割探索にする。

問題設定の変種

$f \colon \mathbb{R} \to \mathbb{R} \cup \lbrace + \infty \rbrace$ が下に凸かつ狭義単調増加で、 $g (p) = \inf \limits _ x \left ( f(x) - px \right )$ が高速に計算できるとする。与えられた $k$ に対し、 $f \left ( \tilde x \right ) = k$ を満たす $\tilde x$ を求めよ。

$f$ が離散ではなく連続になっていることに注意。これは $f \left ( \tilde x \right ) = k$ となる $\tilde x$ が存在した方が議論が簡潔になるためであり、離散の設定なら線形に連続に拡張してしまえば良い。

ペナルティ回数の管理, 傾き二分探索

$x ^ {\ast} _ {p}$ が分かれば $g (p) = f \left ( x ^ {\ast} _ p \right ) - p x ^ {\ast} _ p$ から $f \left ( x ^ {\ast} _ p \right )$ が分かるため、二分探索を行うことができる。

三分探索, 黄金分割探索

まず、 $f$ を平行移動することで $k = 0$ とする。すると、 $f(x)$ のグラフと $x$ 軸との交点の $x$ 座標を求める問題となる。

$f$ の $x$ 軸との交点における傾き $\tilde p$ を求めることを考える。 $h \colon \mathbb{R} _ {\gt 0} \to \mathbb{R} \cup \lbrace + \infty \rbrace$ を $h(p) = - \dfrac{g (p) }{p}$ で定める。 $h(p)$ は、 $f (x)$ に引いた傾き $p$ の接線の $x$ 切片である。 $f$ が単調かつ凸であるから、 $h$ は単峰で $\tilde p$ において最小値を取り、三分探索を適用することで求まる。このとき $\tilde x = h \left ( \tilde p \right )$ である。

正確には、 $f$ が $x$ 軸との交点において微分可能とは限らないため、 $\tilde p$ は任意の劣勾配ということになる。

注意

二分探索や三分探索の初期値は、問題毎に考えて行うしかない。
$g(p) = - \infty$ の場合 $x ^ {\ast} _ p$ などが定まらないが、これも問題毎に処理する。ただし $f$ の定義域が有界な区間であることが多く、その場合 $g$ は常に有限になる。また、 $g(p) = - \infty$ となるのは $p$ が大きすぎるか小さすぎるかのときなので、 $x ^ {\ast} _ p$ を適切に $\pm \infty$ にすることでも回避できる。