えびちゃんの日記

えびちゃん（競プロ）の日記です。

有理数上の二分探索（ざっくり導入編）

詳しく解説編があるかはわかりません。

下記のような状況に対する別の策です。

rsk0315.hatenablog.com

rsk0315.hatenablog.com

å°Žå…¥

今回は、浮動小数点数をそもそも使わない方針で考えます。

ある（自分で決める）上限 $b$ に対して、分母が $b$ 以下の（既約）分数の集合 $\Q_b$ を考えます*1。 すなわち、$\Q_b = \{p/q \mid 0\lt q\le b\}$ です。

さて、ある関数 $f\colon \R\to \{\top, \bot\}$ であって、次の条件を満たすものを考えます*2。

  • $\alpha\in\R$ が存在し、$f(x) = \top \iff x \le \alpha$ が成り立つ。

このとき、$\Q_b$ の要素のうち $\alpha$ に最も近い要素を求めてみましょうという話です。 $\alpha_{\top} \triangleq \max\,\{r\in\Q_b\mid f(r) = \top\}$ と、$\alpha_{\bot} \triangleq \min\,\{r\in\Q_b\mid f(r) = \bot\}$ を求めます*3。

$\alpha - \alpha_{\top}$ と $\alpha_{\bot} - \alpha$ は、それぞれ $1/b$ で抑えられます。

誤差に関する話

$0\lt\varepsilon\lt 1/b$ に対して $\alpha = 1/b-\varepsilon$ のとき、$\alpha_{\top} = 0$ であり、$\alpha - \alpha_{\top} = 1/b - \varepsilon$ です。 $\varepsilon$ はいくらでも小さくできるので、最悪時には少なくとも $1/b$ 程度の誤差が生じます。

一方、ある $i$ に対して $i/b \le \alpha \lt (i+1)/b$ が成り立ち、$i/b$ と $(i+1)/b$ は $\Q_b$ に属するため、誤差は $1/b$ で上から抑えられます。

$\alpha_{\bot}$ に対しても対称な議論を適当にやればいいので同じです。

紹介

これは、Stern–Brocot tree という木を用いることで可能です。

読み方に関して

Moritz Stern さんはドイツの方で、「しゅてぁん」みたいな読み方をする気がします。場合によっては「しゅてるん」に近いかもしれません？ Achille Brocot さんはフランスの方で、「ぶろこ」みたいな読み方をする気がします。

フランス語の sans や tableaux のような単語は（リエゾンが起きない限り）末尾の /z/ を読まないと思うのですが、英語でそれらの単語を使うときは /z/ の発音をするみたいです。 Paris のような固有名詞でも英語では末尾の /s/ を読むみたいです。固有名詞ではリエゾンは起きないらしいです。最近知りました。 フランスのお方の名前を英語文脈で読むとき、末尾の発音などが変わったりするのでしょうか。もしかすると末尾以外もたくさん変わるかもしれません。Michael さんとかはどういう呼ばれ方をするものなのでしょう。

Stern–Brocot tree

$\Q_{14}$ の要素からなる Stern–Brocot tree の（$0$ 以上 $1$ 以下の部分の）図です。図が大きくて字が小さいので、適宜拡大したりして見てください。 文字がつぶれてて見えなかったら下記の画像ツイートなども参考にしてください。

Stern–Brocot tree は有理数の頂点からなる二分木です。 ある頂点 $m/n$ の左の子は次のように定まります。

  • $m/n$ から上に順に辿っていったとき、$m/n$ より小さい値であって最初に見つかるものを $m'/n'$ とおく。
  • このとき、$m/n$ の左の子を $(m+m')/(n+n')$ とする。

右の子も同様に定義します。 たとえば、$3/7$ から上に辿って最初に現れる $3/7$ より大きい頂点は $1/2$ なので、$3/7$ の右の子は $4/9$ となります。

より詳細に

$3/7$ と書かれている頂点から上に辿って最初に現れる左側の頂点が $2/5$、右側が $1/2$ です。この頂点では値 $3/7$ を持ちつつ、$( (2, 5), (1, 2))$ という値も管理しています。$3/7 = (2+1)/(5+2)$ です。左の子は $( (2, 5), (3, 7))$ で $5/12$、右の子は $( (3, 7), (1, 2))$ で $4/9$ となります。

描いたりしながらじゃないとイメージがつきにくいかもしれないので、各々描きながらイメージしてほしいです。

この情報を管理することで、根から始めて左右の子を求めながら探索できます。根は $( (0, 1), (1, 0))$ で $1/1$ です。根の右には $1$ より大きい数が現れます。また $1/0 = \infty$ とします。

さて、$m/n$ から左の $k$ 回進んだ頂点は $(m+km')/(n+kn')$ になります。 このことから、同じ方向に潜っても分母は線形でしか増えないことがわかります（愚直に一つずつ潜ろうとすると $\Theta(b)$ 回の潜りが発生するケースがある*4）。 一方、$1/1$ からじぐざぐに（左右に 1 回ずつ交互に）潜っていくと分母に Fibonacci 数列が現れることからなんとなくわかるように、進む方向が変わるごとに指数的に増えていきます。ちゃんとした証明は参考文献に挙げるリンクを読んでください。

そういうわけで、$O(\log(b))$ 回だけ「ここまで潜っても $\alpha$ をまたがないかな？」というのを探索することで、$(\alpha_{\top}, \alpha_{\bot})$ を求められます。実際には、$f(m/n) = f( (m+km')/(n+kn'))$ かな？というのを $k$ に対して指数探索します（$n+kn'\gt b$ になったら打ち切り）。

指数探索については ↓ などを読むといいかもしれません。 rsk0315.hatenablog.com

指数探索を $O(\log(b))$ 回やっても、$O(\log(b)^2)$ ではなく $O(\log(b))$ で抑えられる証明も、参考文献のリンクにあります。

よって、上記を適切に整理することで、$O(\log(b))$ 回の $f$ の計算によって $(\alpha_{\top}, \alpha_{\bot})$ を求めることができます。 特に、$(\alpha_{\top}+\alpha_{\bot})/2$ は、$\alpha$ との絶対誤差が $1/2b$ 以下の値です。

実装について補足

頂点で管理している値を $( (m_L, n_L), (m_R, n_R))$ のとき、対応する有理数は $(m_L+m_R)/(n_L+n_R)$ ですが、$n_L+n_R\gt b$ のとき $(\alpha_{\top}, \alpha_{\bot}) = (m_L/n_L, m_R/n_R)$ となります。

指数探索をしていて $n_L+kn_R\gt b$ になったら、（算数で適当な $k$ を求めて）$\alpha_{\top} = (m_L+km_R)/(n_L+kn_R)$ とわかり、$\alpha_{\bot} = m_R/n_R$ とわかります。左右逆に潜っているときは逆の感じになります。

関連する問題

そもそも有理数でやってもしょうがない問題（判定関数の中で三角関数が出てくるとか）ではあまり役に立たない気がします。

参考文献

ぽかいこちゃんの実装とえびちゃんの実装は仕様が違うので注意が必要そうです。 また、えびちゃんは Rust だし、ぽかいこちゃんの C++ は比較的クセが強めだし、多くの競プロ er の写経には向いていなさそうです。各々がんばって実装してください。

その他関連する話

おわり

つかれちゃいました。

*1:この記法はおそらく一般的なものではなく、この記事の中でえびちゃんが勝手に使っているだけだと思います。

*2:$\top$ は true、$\bot$ は false のことだと思ってください。

*3:ここでは $\alpha\in\R$ としているので両方の集合は空にはならないが、$\alpha = \infty$ だったりして片方が空になる場合はよしなにしてください。

*4:というのは嘘で、整数部分が確定するまでは分母が増えないので、$O(\floor{\alpha}+b)$ 回？