抽象化ライブラリの第一歩としての二分探索

「競プロライブラリにおける抽象化と言えばセグ木」みたいな風潮ができてから久しいですが、二分探索に関してそうした抽象化を意識している人はあまり多くない気がしています。

おきもち

たとえば、「ソートされた配列が欲しい」の気持ちのときにいちいちソートの実装を書かされるのはうれしくないはずです。 main 関数にいちいちソートの実装をベタ書きしている人も滅多にいないでしょう。

あるいは、「$0$ 以上 $n$ 未満の整数を順に回したい」と思っているときに「まず $i = 0$ で初期化する。$i \lt n$ である間、$i \xgets+ 1$ で更新する」という “内部実装” を書く必要があるのもうれしくないです。C++ 系の言語を使っていて REP マクロを使っていない人にとっては、そういうベタ書きは当然のものだと思われているでしょうが、ちょっと落ちついて考え直してみてほしいです*1。

二分探索に関しても同様です。 main 関数内での気持ちとしては「何々の条件を満たす最大の値が欲しい」などだけであって、それをするための内部実装をいちいち書くのはうれしくないです。

また、思考のレイヤーの観点の他にも、（たとえば二分探索の内部で二分探索をする必要がある場合などに）変数名をいちいち気にする必要があるのもベタ書きの嫌なポイントです。

競プロ er あるある言説として「ゆーても数行で書けるし」のようなものがありますが、5 行で書けるのと関数呼び出し 1 つで書けるのとでは、やはり手軽さが違うとも思います。

整理・設計

さて、二分探索でやっていることを考えましょう。 状況設定によって二分法と呼び分ける派閥もありますが、ここでは “その手のやつ” たちを二分探索と称することにします。

一旦ここでは整数に限った話をします。界隈でよく言われているような設定は下記でしょう。

$\gdef\boolty{\{\top, \bot\}}$

• input
  • $x_L\in\Z$,
  • $x_U\in\Z$,
  • $f\colon \Z\to\boolty$.
• precondition
  • $x_L \lt x_U$,
  • $f(x_L) = \top$,
  • $f(x_U) = \bot$,
  • $f(x) = \bot \implies f(x+1) = \bot$.
• output
  • $x\in[x_L\lldot x_U]$.
• postcondition
  • $f(x) = \bot$,
  • $f(x-1) = \top$.

ここで、$\top$, $\bot$ は true, false に相当する記号です。 $f(x) = \bot \implies f(x+1) = \bot$ は、界隈で「単調性」と言われがちな条件です。

「単調性」？

ソート済み（単調増加）の列から値を探すときに二分探索を探すというのが基本的な用法としてあり、そこから「単調」と呼ばれるようになったんだろうと思っていました。 とはいえ、[true, true, ..., true, false, ..., false] みたいな配列を称する呼び方として「単調性」は自然なものかね？という気持ちがありました。

なのですが、調べてみた感じだと、そういう用法もあるらしく、ならまぁいいか〜という気持ちになりました。 en.wikipedia.org $\eod$

ところで、二分探索のアルゴリズムで上記の事後条件を満たすような $x\in[x_L\lldot x_U]$ を返すためには、単調性の条件は必要ないことに気づきます。

界隈では「二分探索を用いて境界を見つけるためには単調性が必要である」と言われがちですが、自分の解釈としては、「二分探索を行うと true・false を跨ぐ箇所を一つ見つけることができる。単調性があればそれが一意であることがわかるが、二分探索の実行可能性自体には影響しない」という感じです。

それを踏まえて、下記のような設計でいきます。$f(x_L) = \top$ の条件も除いてしまう方が便利な状況もあるのでそうします*2。

• input
  • $x_L\in\Z$,
  • $x_U\in\Z$,
  • $f\colon \Z\to\boolty$.
• precondition
  • $x_L \le x_U$,
  • $f(x_U) = \bot$.
• output
  • $x\in[x_L\lldot x_U]$.
• postcondition
  • $f(x) = \bot$,
  • $x = x_L \vee f(x-1) = \top$.

$f(x) = \top$ となる方が自然に見える気もしつつ、「（典型的な状況として）$[x_L\lldot x)$ では条件がよい感じで、$[x\lldot x_U)$ だとうれしくない感じになる」のようなイメージでやっていることが多く、こうした設計をしています。 ここは各々が好みに合わせて行えばいいと思います。

実装

そういうわけで、$x_L$, $x_U$, $f$ を渡すと、上記の事後条件を満たすような $x$ を返してくれるようなライブラリを作りたくなってきます。

主要どころということで、Rust, C++, Python の例を挙げてみようと思います。 はてなブログに貼りつけても見にくい感じがあるので、AtCoder への実際の提出コードを貼ります。

• 提出 #56338171, Rust
• 提出 #56335984, C++
• 提出 #56336232, Python

その他

実装に関して

$x_U$ を渡さず、指数探索を行う方針のライブラリを作ってもよいでしょう。えびちゃんはよくこちらを使っています。

思考停止で適当な定数の INF を使うよりは失敗が少ないと思います。 有限値で $\infty$ を代替するときは、思考停止で（≒ 問題ごとに条件を意識せず）使うのではなく、妥当な値であることを都度考える必要があると思っています。

rsk0315.hatenablog.com

中間値に関して

できるだけ、オーバーフローに気をつける実装にしておきましょう。 わざわざライブラリ側で「こういう状況ではバグるんだけど、まぁどうせ競プロで問題になることは少ないし平気」のような欠陥を残しておくメリットは少ないです。 あとそういう欠陥があること自体を忘れがちなので。

意識したことがない人は多いのかもしれませんが、たとえば 1_000_000_000_i32 と 2_000_000_000_i32 の平均値を求めようとする際、単にこれらを足し合わせると i32 ではオーバーフローします。(low + high) / 2 ではなく low + (high - low) / 2 のようにする方針が有名です。ループ条件にも high - low > 1 なので、そういう意識のしやすさもあります。

とはいえこれで満足することもできません。-2_000_000_000_i32 と 2_000_000_000_i32 の差もやっぱりオーバーフローします。 符号つき整数の平均値？ どうするのがいいんでしょう。

C++20 では midpoint という関数が用意されています。

Rust の std の実装では、fn map(a: $SignedTy) -> $UnsignedTy; と fn demap(a: $UnsignedTy) -> $SignedTy; を定義し、下記のようにしているようです (core/num/int_macros.rs, int_impl!)。

demap(<$UnsignedTy>::midpoint(map(self), map(other)))

符号なしに関しては、自分より大きい型にキャストして計算したり、u128 に関しては有名な overflow-free なアルゴリズム ((a ^ b) >> 1) + (a & b) を使っているようです(core/num/mod.rs, midpoint_impl!)。

上記の提出コードでは、過度に複雑になるのを防ぐため、符号なし整数のことだけを考えています。

お気持ちに関して

そもそも、ベタ書きであれライブラリを使うのであれ、二分探索を終えた後に事後条件を意識するのが大事です。 これをしないことには、何回繰り返したところで「勘でやっている」のと大差ないと思います。

もっとも、事前条件・事後条件を意識する必要があるのは二分探索に限らず、すべてのアルゴリズム・データ構造が当てはまるとは思います。

めぐる式に関して

ライブラリ化してしまえば、「毎回二分探索でバグらせています」「めぐる式を使っていますか？」のような会話をいちいちする必要もなくなるだろうなと思っています。

勘違いされていることが多いですが、そもそも めぐる式二分探索の原典 は、[low, high) を半開区間で持つことだけを指しているのではないです。 変数名で区間を [ok, ng)・(ng, ok] のように明示し、どちらの場合でもループの式を abs(ok - ng) > 1 のように統合してしまうもので、なかなか過激なスタイルです。

mid = (ok + ng) / 2 はオーバーフローが怖いです。あと if (solve(mid)) の部分はあんまりうまくない名称な気がします。これはえびちゃんの感情です。

そもそも、にぶたんの下界・上界の部分を「区間」と捉えるの自体がえびちゃんの感覚とあってないかも？

ライブラリ・スニペットに関して

にぶたん（や、その他のアルゴリズム）のテンプレとして下記のようなスニペットを都度貼りつけている人もいるでしょう。

let (mut ok, mut bad) = (0, INF);
while bad - ok > 1 {
    let mid = ok + (bad - ok) / 2;
    let mid_is_ok = {
        // ここに実装を書く
    };
    *(if mid_is_ok { &mut ok } else { &mut bad }) = mid;
}

こういうやり方をやめましょうと主張する気はないですが、あまり好ましいとも思っていません。 「このような引数を渡すと、こういうものを返す」という形式で整理できていないもの・それが難しいものに関してはこれで妥協するのもありですが、事前条件・事後条件の意識などがしにくくなりそうという気がしています。

同様のものとして、BFS なども適切に抽象化できるとうれしいかもしれません*3。

類題

ネタバレになるのであまり好ましくないかもではありますが、そもそも ABC の問題数はたくさんあるので「方針をわかった上できちんと実装を詰める用」と「方針を自力で考える用」で分けて使ってしまってもよい気がします。

ざっと探した感じでも、ABC 300 以降で 2 割くらいのコンテストでは出ているようで、常連さんだなぁという気持ちです。 ところで、ABC 300 がすでに 1 年以上前ということに気づいてびっくりしてしまいました。

• ABC 302 D
• ABC 311 E
• ABC 312 C
• ABC 313 C
• ABC 318 F
• ABC 319 D
• ABC 321 D
• ABC 330 F
• ABC 341 D
• ABC 346 F
• ABC 353 C
• ABC 364 D
• ABC 365 C

所感

ベタ書きしたがる人々を改宗させるのは大変そう。

最近はどうかわからないですが、競プロ界隈の一部では「パソコンや言語仕様に詳しくなく、そうしたものを使って高度に便利なライブラリ・ツールを準備することに対する忌避感がある」のような風潮があったように感じます。 oj やその類のテストツールを使わずに手作業でがんばっている人はまだまだたくさんいるような気がします*4。

おわり

ああ我らの日曜日。

*1:別に REP マクロを推奨したいわけではないですが、ベタ書きを推奨したいわけでもありません。

*2:$f(x_L-1) = \top$ であると見なしているという見方もあるかも。

*3:ありがちなグラフに限った BFS という意味ではなく、一般の探索ということです。

*4:そういえば、これ にレスがなくてかなしい。