問題概要
一発書きで fastest （2024/08/27）になったのは意外でした．
解法
以下，有理数と言えば非負であることを仮定し，有理数 $a/b$ のような表記はすべて $a,b$ は非負整数で $\gcd(a,b)=1$ を満たすことを仮定します．また便宜上 $1/0$ という有理数も考え，これらは任意の非負有理数より大きな有理数（$\infty$）であると考えます．
本問題は形式上は「$x/y$ を近似する」という形になっていますが，より一般に次の形に一般化して解くことができますし，実用上も役に立つと思います．
有理数を引数として bool 値を返す関数 $\mathrm{check}(a/b)$ があり，次の意味で単調性があるとする：$T = \{x=a/b\mid \mathrm{check}(a/b)=\mathrm{true}\}$, $T = \{x=a/b\mid \mathrm{check}(a/b)=\mathrm{false}\}$ とするとき，$0/1\in T$, $1/0\in F$ かつ任意の有理数 $x,y$ に対して $x\in T, y\in F$ ならば $x<y$．
このとき有理数集合 $S = \{a/b\mid a,b\leq N\}$ は有限集合で，$0/1\in S\cap T$ および $1/0\in S\cap F$ であるから $\max (S\cap T)$ および $\min (S\cap F)$ が存在する．これらを求めよ．
計算量解析において，$\mathrm{check}(a/b)$ の呼び出しは $O(1)$ 時間であると仮定します．
まず Stern-Brocot 木をたどれば，次のようなアルゴリズムが考えられます：
- $x_1=a_1/b_1=0/1$, $x_2=a_2/b_2=1/0$ で初期化する．
- $\max(a_1+a_2,b_1+b_2)\leq N$ である限り次を行う：
- $\mathrm{check}(a_1+a_2,b_1+b_2)=\mathrm{true}$ ならば $x_1=a_1/b_1$ を $(a_1+a_2)/(b_1+b_2)$ に取り換える．
- $\mathrm{check}(a_1+a_2,b_1+b_2)=\mathrm{false}$ ならば $x_2=a_2/b_2$ を $(a_1+a_2)/(b_1+b_2)$ に取り換える．
このとき $x_1 = \max (S\cap T)$ および $x_2 = \min(S\cap F)$ が出力されます．Stern-Brocot 木の性質より，常に次の条件が保たれるからです．
- $x_1 \in T, x_2\in F$ であり，$x_1<x<x_2$ を満たす有理数 $x=a/b$ のうちで $\max(a,b)$ が最小のものは $(a_1+a_2)/(b_1+b_2)$ である．
しかしこのアルゴリズムは最悪ケースで $\Theta(N)$ 時間かかります．
このアルゴリズムを，一方に加算する反復をひとまとめににします．
- $\max(a_1+a_2,b_1+b_2)\leq N$ である限り次を行う：
- $\mathrm{check}(a_1+ka_2,b_1+kb_2)=\mathrm{true}$ かつ $a_1+ka_2\leq N, b_1+kb_2\leq N$ となる最大の $k$ をとり，$x_1=a_1/b_1$ を $(a_1+ka_2)/(b_1+kb_2)$ に取り換える．
- $\mathrm{check}(ka_1+a_2,kb_1+b_2)=\mathrm{false}$ かつ $ka_1+a_2\leq N, b_1+kb_2\leq N$ となる最大の $k$ をとり，$x_2=a_2/b_2$ を $(ka_1+a_2)/(kb_1+b_2)$ に取り換える．
このような $k$ を選択するステップは $\Theta(\log N)$ 回です（常に $k=1$ が選ばれる場合がワーストケースで，その場合の分子・分母はフィボナッチ数列の増大度です）．
本問「Rational Approximation」の場合はこのような「最大の $k$」が $O(1)$ 時間で計算できるため，これで $\Theta(\log N)$ 時間の解法となります．
「最大の $k$」を check 関数呼び出しだけで求めることを考えましょう．例えば $0\leq k\leq N$ の範囲を二分探索するという方法が考えられますが，それではアルゴリズム全体で最悪 $\Theta(\log^2N)$ 時間の計算量になってしまいます．
二分探索を指数探索に変えるだけで，アルゴリズム全体が $\Theta(\log N)$ 時間になります．
つまり，$k=2^i$ が足せなくなるまで $i$ をインクリメントし，足せなくなったら $i$ をデクリメントしながら貪欲に $2^i$ を足していきます．
$a_1/b_1$ に対する $i$ のインクリメントの回数，$a_2/b_2$ に対する $i$ のインクリメント回数をそれぞれ評価すれば，アルゴリズム全体が $\Theta(\log N)$ 時間になることは容易に分かります．
