ABC 333 G — Nearest Fraction

考察

分母の上限内で目標値を下から最も近く挟む分数と、上から最も近く挟む分数を求めれば、答えはその二つのどちらかだ。連分数を使うと、この境界を一方向ずつまとめて進められる。ただし、次の収束分数が分母上限を超えたとき、その一歩手前で止めた中間分数も候補に残す必要がある。

分母を q=1,…,Nq=1,\ldots,N と全探索し、各分母で最も近い分子を選ぶ方法は、N≤1010N\leq 10^{10} では間に合わない。分母を一つずつ増やす代わりに、目標値を挟む境界がどこまで動けるかを調べる。

まず入力小数を文字列として読み、小数点以下の桁列を整数にしたものと、桁数に対応する10の冪を約分する。得られた既約分数を r=R/Dr=R/D とする。例えば末尾に0を含む 0.41000.4100 も 41/10041/100 となる。以後の判定はすべて整数で行い、元の R,DR,D は誤差比較のために保持する。

収束分数の分子と分母を一緒に更新する

連分数 r=[a0;a1,a2,…]r=[a_0;a_1,a_2,\ldots] は、整数部分を取り、残りの逆数について同じ処理を繰り返す表現である。r=R/Dr=R/D なら、作業用整数を (X,Y)=(R,D)(X,Y)=(R,D) とし、係数 ai=⌊X/Y⌋a_i=\lfloor X/Y\rfloor を得るたびに (X,Y)←(Y,X mod Y)(X,Y)\leftarrow(Y,X\bmod Y) とすればよい。本問では 0<r<10<r<1 なので最初の係数は a0=0a_0=0 となる。

係数を aia_i まで使った分数を収束分数 Hi/KiH_i/K_i と呼ぶ。分子 HiH_i と分母 KiK_i は、直前二組から次のように求まる。

Hi=aiHi−1+Hi−2,Ki=aiKi−1+Ki−2H_i=a_iH_{i-1}+H_{i-2},\qquad K_i=a_iK_{i-1}+K_{i-2}

初期値は (H−2,K−2)=(0,1)(H_{-2},K_{-2})=(0,1)、(H−1,K−1)=(1,0)(H_{-1},K_{-1})=(1,0) とする。後者の 1/01/0 は更新式のための形式的な境界であり、出力する分数ではない。最初の更新で H0/K0=0/1H_0/K_0=0/1 となる。

係数列全体は保存せず、次の順で処理する。

  1. 現在の X,YX,Y から ai=⌊X/Y⌋a_i=\lfloor X/Y\rfloor と次の分母 Ki=aiKi−1+Ki−2K_i=a_iK_{i-1}+K_{i-2} を計算する。
  2. Ki>NK_i>N なら、直前二組を更新せず、後述の打切り処理へ進む。
  3. Ki≤NK_i\leq N なら分子 Hi=aiHi−1+Hi−2H_i=a_iH_{i-1}+H_{i-2} も求める。X mod Y=0X\bmod Y=0 なら、この収束分数は rr 自身なので Hi,KiH_i,K_i を出力して終了する。
  4. それ以外では、古い直前の組を二つ前へ、今回の組を直前へ移す。同時に (X,Y)←(Y,X mod Y)(X,Y)\leftarrow(Y,X\bmod Y) とし、添字を一つ進めて手順1へ戻る。

既約分母 D≤ND\leq N の場合は、分母上限を超える前に完全一致で終了する。最初にこの条件を判定して R,DR,D をそのまま返してもよい。

分母上限で係数を途中まで使う

次の収束分数の分母が NN を超えたら、係数 aia_i の代わりに使える最大の整数を求める。

t=⌊N−Ki−2Ki−1⌋t=\left\lfloor\frac{N-K_{i-2}}{K_{i-1}}\right\rfloor

Ki−1=0K_{i-1}=0 となるのは初期の i=0i=0 だけだが、このとき K0=1≤NK_0=1\leq N なので打切り処理には入らない。従ってこの除算を行う時点では Ki−1>0K_{i-1}>0 である。直前二組の分母は上限内なので 0≤t<ai0\leq t<a_i となる。

残す二候補は、直前の収束分数と、係数を tt で止めた分数である。

C=Hi−1Ki−1,T=tHi−1+Hi−2tKi−1+Ki−2C=\frac{H_{i-1}}{K_{i-1}},\qquad T=\frac{tH_{i-1}+H_{i-2}}{tK_{i-1}+K_{i-2}}

後者が中間分数で、t=0t=0 なら二つ前の収束分数になる。二候補は rr を挟むが、どちらが下側かは段数で変わる。分子・分母の交差積で大小を判定し、小さい方を a/ba/b、大きい方を c/dc/d としておけば、最後の同値処理も書きやすい。

独自の小例として r=0.41=41/100,N=3r=0.41=41/100,N=3 を追う。

段 ii係数 aia_i次の収束分数分母上限との比較
000/10/1採用して進む
121/21/2採用して進む
222/52/5分母が3を超えるので打ち切る

収束分数だけなら 0/1,1/20/1,1/2 しか残らない。しかし最後の係数を t=⌊(3−1)/2⌋=1t=\lfloor(3-1)/2\rfloor=1 にすると、中間分数は 1/31/3 となる。0.410.41 からの距離は 1/31/3 が 23/30023/300、1/21/2 が 9/100=27/3009/100=27/300 なので、答えは 1/31/3 だ。次の収束分数を捨てるだけでは、この候補を見落とす。

上下二候補の誤差を厳密に比べる

下側 a/ba/b、上側 c/dc/d の誤差は、それぞれ次の式である。

r−ab=Rb−DaDb,cd−r=Dc−RdDdr-\frac ab=\frac{Rb-Da}{Db},\qquad \frac cd-r=\frac{Dc-Rd}{Dd}

共通の DD を消して交差積を取ると、下側を選ぶ条件は

(Rb−Da)d≤(Dc−Rd)b(Rb-Da)d\leq(Dc-Rd)b

となる。等しいときも下側を選ぶので、問題の「同じ誤差なら小さい分数」という規則を満たす。例えば r=0.45,N=5r=0.45,N=5 では候補が 2/5,1/22/5,1/2、誤差はともに 1/201/20 であり、2/52/5 を出力する。

典型の発動条件

連分数とsemiconvergent

分母上限付きで絶対誤差を最小にしたいときは、連分数の収束分数だけでなく、中間分数(semiconvergent)も調べる。Euclid互除法の一つの商は、隣接境界を同じ方向へまとめて動かす回数に対応する。商を全て使えない最後の段だけ、分母上限から許される最大の回数を計算すればよい。

有理数の厳密比較

有限小数や分数の入力で、最小差や同値の規則まで正確に判定したいときに使う。小数を整数の比へ直し、誤差の分子だけでなく分母も含めて交差積で比べる。必要な整数幅は、最終的な答えではなく比較途中の積から決める。

問題固有の要素

入力が高々18桁の有限小数なので、目標値を近似せずに分数へ変換できる。さらに本問は 0<r<10<r<1 だから、上下の最隣接候補も [0,1][0,1] 内にあり、分子の条件 0≤p≤q0\leq p\leq q を満たす。完全一致がなければ、この二候補を絶対誤差で比較し、同値は下側へ戻す。

正当性

まず収束分数の更新式から、直前二組の行列式の絶対値は常に1である。

∣Hi−1Ki−2−Hi−2Ki−1∣=1\left|H_{i-1}K_{i-2}-H_{i-2}K_{i-1}\right|=1

初期値で成立し、新しい組へ進むと符号だけが反転する。係数を途中の tt に変えても、直前の組との行列式の絶対値は1のままなので、収束分数と中間分数は既約である。完全一致で終了する場合は、分母上限を満たす既約分数で誤差0を達成している。

次に、打切り時の C,TC,T が rr を挟むことを確認する。現在の残りの連分数の値は X/YX/Y であり、次の関数を使うと r=F(X/Y)r=F(X/Y) と書ける。

F(s)=sHi−1+Hi−2sKi−1+Ki−2F(s)=\frac{sH_{i-1}+H_{i-2}}{sK_{i-1}+K_{i-2}}

これは連分数の残りを ss とした表現で、係数を一つ取り出す更新式と対応する。行列式が0でないため FF は分母が正の範囲で狭義単調であり、s→∞s\to\infty で CC に近づく。打切り時には t<ai≤X/Yt<a_i\leq X/Y なので、T=F(t)T=F(t) と CC の間に rr がある。

二候補の分母はともに正で NN 以下である。特に i=1i=1 で打ち切る場合は t=N≥1t=N\geq1 となり、T=1/NT=1/N だから、初期の 1/01/0 は残らない。また tt は許される最大値なので、二候補の分母の和は

Ki−1+(tKi−1+Ki−2)>NK_{i-1}+(tK_{i-1}+K_{i-2})>N

となる。これが「二候補の間をさらに探す必要がない」理由になる。

実際、小さい方を a/ba/b、大きい方を c/dc/d とすると行列式は bc−ad=1bc-ad=1。この間にある既約分数 h/kh/k について、u=ck−dhu=ck-dh、v=bh−akv=bh-ak は正整数であり、

k=ub+vd≥b+d>Nk=ub+vd\geq b+d>N

が成立する。従って両候補の間に分母上限内の分数はない。両候補より外側の分数は、同じ側の候補より rr から遠い。よって答えは上下二候補のどちらかであり、誤差を交差積で比較して、同値なら下側を返せば最適解となる。

実装上の注意

  • 小数は浮動小数点へ変換せず、文字列の桁を整数へ取り込む。末尾の0も桁数に含め、その後に最大公約数で約分する。
  • 直前二組の移動と Euclid互除法の更新は、古い値を使って同時に行う。元の R,DR,D と作業用の X,YX,Y を混同しない。
  • 分母がちょうど NN なら採用して進み、超えたときだけ打ち切る。次段で t=0t=0 となっても、二つ前の分数を候補に残せばよい。
  • N=1N=1 でも同じ手順で 0/1,1/10/1,1/1 を比較できる。既約分母が上限内なら完全一致で返すため、有限連分数の末尾の二通りの表現を別々に試す必要はない。
  • 交差積の各項は高々 DN2≤1038DN^2\leq10^{38} となる。例えば Pythonの整数や C++の符号付き128 bit整数で直接比較できる。C++では最初の乗算より前に型を広げる。64 bitで掛けてから変換しても桁あふれは防げない。

復習の核

  • 分母を全探索できないときは、目標値を挟む隣接分数と、その間の分数に必要な最小分母を考える。
  • 次の収束分数が上限を超えたら、係数を途中まで使った中間分数も残す。0.41,N=30.41,N=3 で 1/31/3 を取り出せるかを確かめる。
  • 誤差の分子だけを比べない。上下の誤差を交差積で比較し、同値では問題の優先規則へ戻る。

計算量と制約

時間

整数の基本演算を O(1)O(1) と数える。入力の整数化は小数の桁数に比例し、高々18桁である。約分と連分数の生成は Euclid互除法により O(log⁡D)O(\log D) 時間。係数一つにつき更新は定数回で、打切りと二候補の比較も一回だけなので、全体で O(log⁡D)O(\log D) 時間。

空間

直前二組、作業用の X,YX,Y、元の R,DR,D と二候補だけを保持するため、補助空間は O(1)O(1)。係数列を保存する必要はない。入力文字列も高々18桁の小数である。

制約との対応

0<r<10<r<1、小数点以下は高々18桁、1≤N≤10101\leq N\leq10^{10}。正確な既約分母は D≤1018D\leq10^{18} なので、商ごとの更新で十分に間に合う。分母上限で打ち切り、出力候補を既約かつ [0,1][0,1] 内に保つことで、0≤p≤q≤N0\leq p\leq q\leq N と gcd⁡(p,q)=1\gcd(p,q)=1 を満たす。整数幅は誤差比較の積まで考慮する。

出典

分類・前提・執筆情報

掲載状態: 収録済み

Nearest Fraction の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 連分数・Stern–Brocotで有理近似する

主題
追加で学ぶ技能
    なし
    既習技能
      なし

      主タグ: 連分数・Stern–Brocot有理近似

      執筆: abc-explanation-author1.1.1 / revision 2

      学習の位置

      体系上の位置: 連分数・Stern–Brocotで有理近似する

      • Euclid互除法・連分数・Stern–Brocotの区間を使い、分母上限下の最良有理近似を求められる。

      この解説で扱わないこと:

      • Stern–Brocot木上の経路・祖先集合は「Stern–Brocot木の経路と祖先」で扱う。本Unitは分母制約の下で近似誤差を最小にする候補の選択を目的とする。

      学習記録

      状況更新: 更新記録なし

      復習設定更新: 更新記録なし

      端末内の保存状態を確認しています。

      要復習一覧 / 学習記録のバックアップ / 解説に戻る

      同じ単元の問題