ランダム三分探索
概要
三分探索するには数列が単峰でなければいけませんが、そうでなくても内分比を乱択で決めて複数回繰り返すことでアタリを引けることがしばしばあります。
例題
解法
$ 1 \to 0 \to 1 と変化させる $ A_k の個数を $ x とします。
$ x が小さいと、$ A_k = 1 なる小さい $ k からのコスト $ C_k を何度も支払うことになり、費用が大きくなりそうです。
一方 $ x が大きいと、そもそも操作回数が増えるので費用が大きくなりそうです。
何の根拠もないですが、なんとなく単峰性がありそうな気がしてきました。
試しに三分探索を書いて提出してみると 21 WA・・・どうやら単峰ではなかったようです。
そこで三分探索における内分点を乱択で選ぶように書き直します：
code:random_ternary_search_min.cpp
template <class S, class T, class FUNC>
pair<S, T> random_ternary_search_min(S l, S r, const FUNC& f) {
Assert(r - l >= 2);
static bool first_call = true;
static mt19937 mt;
static uniform_int_distribution<S> rnd;
if (first_call) {
first_call = false;
mt.seed((int)time(NULL));
rnd = uniform_int_distribution<S>((S)0, (S)INFL);
}
S m1 = l + 1 + rnd(mt) % (r - l - 1);
T f1 = f(m1);
while (r - l > 2) {
S m2 = l + 1 + rnd(mt) % (r - l - 1 - 1);
if (m2 >= m1) m2++;
T f2 = f(m2);
if (m1 > m2) {
swap(m1, m2);
swap(f1, f2);
}
if (f1 > f2) {
l = m1;
m1 = m2;
f1 = f2;
}
else {
r = m2;
}
}
return make_pair(l + 1, f1);
}
後はこれを時間いっぱいまで回し、それらの最小値を出力することで AC できました。
提出
なお、この提出コードに含まれる make_gizagiza_case() を実行すると、ランダム三分探索に対する撃墜ケースを生成できます。
他の使用例
ランダム三分探索を入れ子にして使っています。
二分探索の中でランダム三分探索を使っています。
端のフラットな部分の除去を忘れていましたが、乱択で何とかなりました。
単峰なわけないですが双峰ではありそうなので、乱択でアタリを引く確率は高そうです。
元ポスト