ABC204E - Rush Hour2の解法を一部含みます(というかこれを前提に書いてます)。 三分探索がうまくいかなかったときの気持ちを述べているだけなので、あまり参考にはならないかもしれません。ご了承を。

文脈

辺$i=1, 2, \cdots, M$には重み$C_i$の他に$D_i$というパラメータが存在します。時刻$t$においてその辺を利用する場合は$\lfloor \frac{D}{t+1} \rfloor$の重みが追加で加算されます。各頂点で好きなだけ時間を潰せるとき、頂点$1$から頂点$N$の最短距離を知りたいです。 ある頂点$i$に時刻$t_x$に到達したときに、未達の隣接する頂点に移動するための最短の時刻がわかれば自明にDijkstra法です。よって、以下の問題を考えます。

問題

$f(t) = t + C + \lfloor \frac{D}{t+1} \rfloor$とする。$f(t)$を最小とするような非負整数$t$を求めよ。

三分探索がうまくいかない！

直感的に凸な気がします。$t=0$のときは$\lfloor \frac{D}{t+1} \rfloor$がおおきくなり、反対に$t$が大きくなるとそれはそれで$f(t)$はおおきくなるので。 凸のときはどうすればいいですか？そうですね三分探索です。適当に実装をします。

...(前略)
let mut l = t;
let mut r = INF/10; 

while r - l > 2 {
	let m1 = l + (r - l) / 3;
	let m2 = r - (r - l) / 3;

	if d / (t + 1 + m1) + m1 > d / (t + 1 + m2) + m2 {
		l = m1;
	} else {
		r = m2;
	}
}
...

サンプルが合いました。提出をします。提出

...WAです¹。そんなぁ。とりあえず検索をかけると、記事を見つけます²。

以下の凸or凹関数は全て狭義であることに注意してください！

あ～～～～～～～～～～～～～。もしかして、広義の凸³ではバグりますか？

結論

あまりグダグダと書いていても仕方がないので結論を述べることにします。 問題⁴の正体はそもそも三分探索のアルゴリズムが最小値を求めるアルゴリズムではなく、関数の極値を求めるアルゴリズムである、という点です。

関数が常に狭義単調増加・狭義単調減少のいずれかを取り、かつその範囲で極小を取る点がただ一つであるならばその範囲において極小を取る点が最小を取る点に一致するというだけで、最小値を求めるアルゴリズムではないわけです。

もし広義単調増加(減少)となるような区間が存在すると、それが極値として引っかかるんだなぁというそういう話でした。おしまい。