二分探索の上限を適切に決められずに失敗する人かわいそう

競プロ er の間では、（主に実生活で）最適値を探そうと二分探索をして、上限を大きく取りすぎたために破滅するという定番ネタがあります*1。

あるいは、実際のコンテストでも「上限が小さすぎた」「上限を大きくしすぎたため判定関数内でオーバーフローした」などの失敗をする人はそれなりにいる印象です。 後者は特に、上限を思考停止で 1e9 あるいは 1e18 にしている人にありがちです。

ここでは、「より成功率の高い思考停止の方法」として、指数探索 (exponential search) というのを紹介します。 指数時間かけて全探索するというタイプのギャグではないです。

本題

以下のようなコードを考えます。

let mut ok = 0;
let mut bad = todo!();
while bad - ok > 1 {
    let mid = ok + (bad - ok) / 2;
    *(if pred(mid) { &mut ok } else { &mut bad }) = mid;
}

C++ なら以下のような感じです。

ll ok = 0;
ll bad = TODO();
while (bad - ok > 1) {
    auto mid = ok + (bad - ok) / 2;
    (pred(mid)? ok: bad) = mid;
}

mid = (ok + bad) / 2; でもいいですが、以下の理由からmid = ok + (bad - ok) / 2; を使っています：

• bad がオーバーフローしなければ計算過程でオーバーフローしないこと
  • （ok < 0 の場合は注意が必要です）
• ループ条件で bad - ok を使っているので、それを使う方が直感的な（or 頭にやさしい）気がすること

また、その程度の最適化は人間ではなくコンパイラの役割だろうと考え、>> 1 ではなく / 2 を使っています。

さて、todo の部分を決めるために適当な値を考えるのではなく、次のようにしてみましょう。

let mut ok = 0;
let mut bad = 1;  // <- ! ここを
while pred(bad) { // <- ! 追加
    bad *= 2;     // <- ! する
}                 // <- ! だけ
while bad - ok > 1 {
    let mid = ok + (bad - ok) / 2;
    *(if pred(mid) { &mut ok } else { &mut bad }) = mid;
}

まず 1 で初期化しておき、上限が小さい限り倍々で（= 指数的に）増やしていくというものです。

答えを \(z\) としたとき、以下のうれしさがあります：

• 判定の回数が \(2\log_2(z)+O(1)\) 回になる
  • 上限を決め打ちした場合に比べて最悪時でも高々 2 倍程度の回数にしかならない
• 判定関数の入力値が \(2z\) 以下にしかならない
  • そこでオーバーフローしなければ問題ない
• ふつうの二分探索と比べて追記の差分が小さい
  • pred(mid) の形で呼び出せるものとしたときの話
  • ループ内でベタ書きしていたらつらいけど、それは設計を見直していただいて...

例など

判定関数内で mid * x + y のような値を使うとき、ここがオーバーフローしないように、上限を 1e18 / x 程度にするなどが必要な場合があります。切り捨て切り上げなどの境界で間違えたり、y が大きかったりしてかわいそうになる場合もあります。

atcoder.jp

atcoder.jp

こうしたケースで上記の方法が有効になりえます。 もちろん、オーバーフローに対して完全に思考停止したいなら多倍長整数を使うのがいいとは思いますが、その辺の見極めは各々に任せます。 思考停止で 1e18 にするよりは、よっぽどマシな気はします。

また、思考停止以外の文脈でも有用で、たとえば「ランダム文字列が二つあり、一致する共通接頭辞の長さを二分探索したい」といった状況で、「ランダム文字列なのだから答えは小さいはずで、最初から文字列長を上限としなくてもよさそう」という推測から、高速化を図ったこともありました（若干ネタ記事としての色が強いですが...）。

rsk0315.hatenablog.com

（↑この記事は、ロリハから SA を作れるということ自体よりも、ロリハで辞書順比較も高速に行えるという部分が有用パートな気がします）

あとがき

グオーーのネタに対するマジレス記事のような感じにはしたくありませんでした。 一方で、「にぶたんを実生活でやろうとするとどうしてもグオーーになってしまう」のように思っていそうな初心者の気配を感じることが何度かあったため、書きたくなってしまいました。

指数探索の欠点としては、ツイッター映えしないというのがありますね。

おわり

この記事は Advent Calendar とは一切関係ありません。

*1:いわゆる \ﾎﾞﾝｯ/グオーーーー。ほか多数。