[Library Checker] Rational Approximation

問題概要
解法

問題概要

問題文 → ■
自分の提出 → ■ （35 ms）

一発書きで fastest （2024/08/27）になったのは意外でした．

解法

以下，有理数と言えば非負であることを仮定し，有理数 $a / b$ のような表記はすべて $a, b$ は非負整数で $\gcd (a, b) = 1$ を満たすことを仮定します．また便宜上 $1 / 0$ という有理数も考え，これらは任意の非負有理数より大きな有理数（ $\infty$ ）であると考えます．

本問題は形式上は「 $x / y$ を近似する」という形になっていますが，より一般に次の形に一般化して解くことができますし，実用上も役に立つと思います．

有理数を引数として bool 値を返す関数 $check (a / b)$ があり，次の意味で単調性があるとする： $T = {x = a / b ∣ check (a / b) = true}$ , $T = {x = a / b ∣ check (a / b) = false}$ とするとき， $0 / 1 \in T$ , $1 / 0 \in F$ かつ任意の有理数 $x, y$ に対して $x \in T, y \in F$ ならば $x < y$ ．
このとき有理数集合 $S = {a / b ∣ a, b ≦ N}$ は有限集合で， $0 / 1 \in S \cap T$ および $1 / 0 \in S \cap F$ であるから $max (S \cap T)$ および $min (S \cap F)$ が存在する．これらを求めよ．

計算量解析において， $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}) ≦ N$ である限り次を行う：
- $check (a_{1} + a_{2}, b_{1} + b_{2}) = true$ ならば $x_{1} = a_{1} / b_{1}$ を $(a_{1} + a_{2}) / (b_{1} + b_{2})$ に取り換える．
- $check (a_{1} + a_{2}, b_{1} + b_{2}) = 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})$ である．

しかしこのアルゴリズムは最悪ケースで $Θ (N)$ 時間かかります．

このアルゴリズムを，一方に加算する反復をひとまとめににします．

$max (a_{1} + a_{2}, b_{1} + b_{2}) ≦ N$ である限り次を行う：
- $check (a_{1} + k a_{2}, b_{1} + k b_{2}) = true$ かつ $a_{1} + k a_{2} ≦ N, b_{1} + k b_{2} ≦ N$ となる最大の $k$ をとり， $x_{1} = a_{1} / b_{1}$ を $(a_{1} + k a_{2}) / (b_{1} + k b_{2})$ に取り換える．
- $check (k a_{1} + a_{2}, k b_{1} + b_{2}) = false$ かつ $k a_{1} + a_{2} ≦ N, b_{1} + k b_{2} ≦ N$ となる最大の $k$ をとり， $x_{2} = a_{2} / b_{2}$ を $(k a_{1} + a_{2}) / (k b_{1} + b_{2})$ に取り換える．

このような $k$ を選択するステップは $Θ (\log N)$ 回です（常に $k = 1$ が選ばれる場合がワーストケースで，その場合の分子・分母はフィボナッチ数列の増大度です）．

本問「Rational Approximation」の場合はこのような「最大の $k$ 」が $O (1)$ 時間で計算できるため，これで $Θ (\log N)$ 時間の解法となります．

「最大の $k$ 」を check 関数呼び出しだけで求めることを考えましょう．例えば $0 ≦ k ≦ N$ の範囲を二分探索するという方法が考えられますが，それではアルゴリズム全体で最悪 $Θ (\log^{2} N)$ 時間の計算量になってしまいます．

二分探索を指数探索に変えるだけで，アルゴリズム全体が $Θ (\log N)$ 時間になります．

つまり， $k = 2^{i}$ が足せなくなるまで $i$ をインクリメントし，足せなくなったら $i$ をデクリメントしながら貪欲に $2^{i}$ を足していきます．

$a_{1} / b_{1}$ に対する $i$ のインクリメントの回数， $a_{2} / b_{2}$ に対する $i$ のインクリメント回数をそれぞれ評価すれば，アルゴリズム全体が $Θ (\log N)$ 時間になることは容易に分かります．