考察
分母の上限内で目標値を下から最も近く挟む分数と、上から最も近く挟む分数を求めれば、答えはその二つのどちらかだ。連分数を使うと、この境界を一方向ずつまとめて進められる。ただし、次の収束分数が分母上限を超えたとき、その一歩手前で止めた中間分数も候補に残す必要がある。
分母を と全探索し、各分母で最も近い分子を選ぶ方法は、 では間に合わない。分母を一つずつ増やす代わりに、目標値を挟む境界がどこまで動けるかを調べる。
まず入力小数を文字列として読み、小数点以下の桁列を整数にしたものと、桁数に対応する10の冪を約分する。得られた既約分数を とする。例えば末尾に0を含む も となる。以後の判定はすべて整数で行い、元の は誤差比較のために保持する。
収束分数の分子と分母を一緒に更新する
連分数 は、整数部分を取り、残りの逆数について同じ処理を繰り返す表現である。 なら、作業用整数を とし、係数 を得るたびに とすればよい。本問では なので最初の係数は となる。
係数を まで使った分数を収束分数 と呼ぶ。分子 と分母 は、直前二組から次のように求まる。
初期値は 、 とする。後者の は更新式のための形式的な境界であり、出力する分数ではない。最初の更新で となる。
係数列全体は保存せず、次の順で処理する。
- 現在の から と次の分母 を計算する。
- なら、直前二組を更新せず、後述の打切り処理へ進む。
- なら分子 も求める。 なら、この収束分数は 自身なので を出力して終了する。
- それ以外では、古い直前の組を二つ前へ、今回の組を直前へ移す。同時に とし、添字を一つ進めて手順1へ戻る。
既約分母 の場合は、分母上限を超える前に完全一致で終了する。最初にこの条件を判定して をそのまま返してもよい。
分母上限で係数を途中まで使う
次の収束分数の分母が を超えたら、係数 の代わりに使える最大の整数を求める。
となるのは初期の だけだが、このとき なので打切り処理には入らない。従ってこの除算を行う時点では である。直前二組の分母は上限内なので となる。
残す二候補は、直前の収束分数と、係数を で止めた分数である。
後者が中間分数で、 なら二つ前の収束分数になる。二候補は を挟むが、どちらが下側かは段数で変わる。分子・分母の交差積で大小を判定し、小さい方を 、大きい方を としておけば、最後の同値処理も書きやすい。
独自の小例として を追う。
収束分数だけなら しか残らない。しかし最後の係数を にすると、中間分数は となる。 からの距離は が 、 が なので、答えは だ。次の収束分数を捨てるだけでは、この候補を見落とす。
上下二候補の誤差を厳密に比べる
下側 、上側 の誤差は、それぞれ次の式である。
共通の を消して交差積を取ると、下側を選ぶ条件は
となる。等しいときも下側を選ぶので、問題の「同じ誤差なら小さい分数」という規則を満たす。例えば では候補が 、誤差はともに であり、 を出力する。
典型の発動条件
連分数とsemiconvergent
分母上限付きで絶対誤差を最小にしたいときは、連分数の収束分数だけでなく、中間分数(semiconvergent)も調べる。Euclid互除法の一つの商は、隣接境界を同じ方向へまとめて動かす回数に対応する。商を全て使えない最後の段だけ、分母上限から許される最大の回数を計算すればよい。
有理数の厳密比較
有限小数や分数の入力で、最小差や同値の規則まで正確に判定したいときに使う。小数を整数の比へ直し、誤差の分子だけでなく分母も含めて交差積で比べる。必要な整数幅は、最終的な答えではなく比較途中の積から決める。
問題固有の要素
入力が高々18桁の有限小数なので、目標値を近似せずに分数へ変換できる。さらに本問は だから、上下の最隣接候補も 内にあり、分子の条件 を満たす。完全一致がなければ、この二候補を絶対誤差で比較し、同値は下側へ戻す。
正当性
まず収束分数の更新式から、直前二組の行列式の絶対値は常に1である。
初期値で成立し、新しい組へ進むと符号だけが反転する。係数を途中の に変えても、直前の組との行列式の絶対値は1のままなので、収束分数と中間分数は既約である。完全一致で終了する場合は、分母上限を満たす既約分数で誤差0を達成している。
次に、打切り時の が を挟むことを確認する。現在の残りの連分数の値は であり、次の関数を使うと と書ける。
これは連分数の残りを とした表現で、係数を一つ取り出す更新式と対応する。行列式が0でないため は分母が正の範囲で狭義単調であり、 で に近づく。打切り時には なので、 と の間に がある。
二候補の分母はともに正で 以下である。特に で打ち切る場合は となり、 だから、初期の は残らない。また は許される最大値なので、二候補の分母の和は
となる。これが「二候補の間をさらに探す必要がない」理由になる。
実際、小さい方を 、大きい方を とすると行列式は 。この間にある既約分数 について、、 は正整数であり、
が成立する。従って両候補の間に分母上限内の分数はない。両候補より外側の分数は、同じ側の候補より から遠い。よって答えは上下二候補のどちらかであり、誤差を交差積で比較して、同値なら下側を返せば最適解となる。
実装上の注意
- 小数は浮動小数点へ変換せず、文字列の桁を整数へ取り込む。末尾の0も桁数に含め、その後に最大公約数で約分する。
- 直前二組の移動と Euclid互除法の更新は、古い値を使って同時に行う。元の と作業用の を混同しない。
- 分母がちょうど なら採用して進み、超えたときだけ打ち切る。次段で となっても、二つ前の分数を候補に残せばよい。
- でも同じ手順で を比較できる。既約分母が上限内なら完全一致で返すため、有限連分数の末尾の二通りの表現を別々に試す必要はない。
- 交差積の各項は高々 となる。例えば Pythonの整数や C++の符号付き128 bit整数で直接比較できる。C++では最初の乗算より前に型を広げる。64 bitで掛けてから変換しても桁あふれは防げない。
復習の核
- 分母を全探索できないときは、目標値を挟む隣接分数と、その間の分数に必要な最小分母を考える。
- 次の収束分数が上限を超えたら、係数を途中まで使った中間分数も残す。 で を取り出せるかを確かめる。
- 誤差の分子だけを比べない。上下の誤差を交差積で比較し、同値では問題の優先規則へ戻る。
計算量と制約
時間
整数の基本演算を と数える。入力の整数化は小数の桁数に比例し、高々18桁である。約分と連分数の生成は Euclid互除法により 時間。係数一つにつき更新は定数回で、打切りと二候補の比較も一回だけなので、全体で 時間。
空間
直前二組、作業用の 、元の と二候補だけを保持するため、補助空間は 。係数列を保存する必要はない。入力文字列も高々18桁の小数である。
制約との対応
、小数点以下は高々18桁、。正確な既約分母は なので、商ごとの更新で十分に間に合う。分母上限で打ち切り、出力候補を既約かつ 内に保つことで、 と を満たす。整数幅は誤差比較の積まで考慮する。
出典