公式解説 のアルゴリズム自体は既知の前提とします。

※ 一般論として、なるべく浮動小数点数での計算を避け、できるだけ整数で計算できるように考察・式変形するのが定石です。

※ （俗に eps と呼ばれることの多い）微小な値を足すことで計算結果を補正するテクニックが使える場合もありますが、どの程度の大きさにするのが適切かは問題に応じて変わり、簡単にわかるものではないため、小手先の戦術として身につけようとするのは（個人的には）あまりおすすめしないです。

---

各 \(i\) で計算した \(h\) の最大値が答えとなるため、一つの \(h\) の計算における誤差を考えればよく、\(N=2\) のケースを構築します。

以下、浮動小数点数は IEEE 754 の 64-bit のものを考えます（特に、丸め方向は tiesToEven とします）。

浮動小数点数における四則演算を、\(\oplus\), \(\ominus\), \(\otimes\), \(\oslash\) とします（通常の数式で使う \(+\), \(-\) などは、誤差が出ない計算を意味するとします）。

\[ h = \frac{-(H_i-H_{i+1})X_i}{X_i-X_{i+1}}+H_i = \frac{H_{i+1}X_i-H_iX_{i+1}}{X_i-X_{i+1}} \]

を

\[ (-((H_i\ominus H_{i+1})\oslash(X_i\ominus X_{i+1}))\otimes X_i)\oplus H_i \]

として計算する場合と、

\[ ((H_{i+1}\otimes X_i)\ominus(H_i\otimes X_{i+1}))\oslash(X_i\ominus X_{i+1}) \]

として計算する場合について考えます。 後者は、公式解説における「[…]の形で分子と分母をそれぞれ整数型で計算し、」の部分をそれぞれ浮動小数点型で計算してしまった場合に相当します。

浮動小数点数の四則演算は結合法則が成り立たないため、括弧を明示しています。

実数 \(x\), \(y\) に対応する浮動小数点数 \(\hat x\), \(\hat y\) について、\(\hat x\) や \(\hat y\) に誤差が含まれる場合、\(x-y\) と \(\hat x\ominus\hat y\) の相対誤差は基本的に大きくなり得ます。

---

簡潔さのため、\((H_{i+1}, H_i, X_{i+1}, X_i) = (a, b, c, d)\) として記載します。\(c\ge d\) に注意しておきます。

(1) \((-((b\ominus a)\oslash(d\ominus c))\otimes d)\oplus b\)

浮動小数点数の組 \((x, y)\) であって、\(((x\oslash y)\otimes y) \gt x\) となるようなものを考えます。無限精度であれば \(\frac xy\times y = x\) なので、ここから \(x\) を引くことで符号を誤らせることができます。

こうした組は多数あり、たとえば全探索などで簡単に探すことができます。小さい例として \((x, y) = (3, 187)\) のとき下記が成り立ちます。

\[ (3\oslash187)\otimes 187 = 3+2^{-51} \gt 3. \]

これを前提として、下記のように構築することができます。

\[ (\underbrace{-((b\ominus a)\oslash(d\ominus c))\otimes d}_{-(3\oslash 187)\otimes 187}) \oplus \underbrace{b\vphantom f}_3 = -2^{-51} \lt 0. \]

\(d\le c\) を踏まえて、\((b, d, b\ominus a, d\ominus c) = (3, 187, -3, -187)\) とすればよく、\((a, b, c, d) = (6, 3, 374, 187)\) とできます。

あるいは、大きい例として \((x, y) = (499999999, 11)\) も挙げられます。

\[ 499999999\oslash11\otimes11 = 499999999+2^{-24} \gt 499999999. \]

よって、先ほど同様にして、\((a, b, c, d) = (999999998, 499999999, 22, 11)\) とできます。

あるいは、\(2^{-24} \approx 6\cdot 10^{-8} \gt 10^{-9}\) なので、-1 の判定誤りでない例を作ることも可能です。\((a, b, c, d) = (999999999, 500000000, 22, 11)\) とできます。真値が \(1\) なのに対して \(1-2^{-24}\) を出力してしまいます。

（追記） また、逆方向への誤差の例として \(499999999\oslash39\otimes39 = 499999999-2^{-24} \lt 499999999\) も挙げられます。

ケースとしては次のようになります。

2
187 3
374 6

2
11 499999999
22 999999998

2
11 500000000
22 999999999

2
39 499999999
78 999999998

2
39 500000000
78 999999999

（おまけ）同様の考え方を用いて、Python の Decimal（のデフォルトの精度）での実装も、次のケースで落とすことができます。

2
14 2
28 4

（おまけ）同様に、long double（AtCoder 環境では 80-bit）用のケースも構築可能です。

2
45 3
90 6

(2) \(((a\otimes d)\ominus(b\otimes c))\oslash(d\ominus c)\)

\(a\times d \lt b\times c\) かつ \(a\otimes d = b\otimes c\) となる組を構築できれば十分です。-1 と出力すべき部分で 0.0 としてしまうためです。

\(10^9\) 以下の正整数の積として表せる相異なる整数のペアであって、浮動小数点数で計算すると同じ整数に丸められてしまうものを考えます。

浮動小数点数として表したときに誤差が出る整数は \(2^{53}+1 = 9007199254740993\) 以上であるため、それらの整数を素因数分解してみます。

\[ \begin{aligned} 2^{53}+1 = 9007199254740993 &= 3\times 107\times 28059810762433, \\ \vdots\qquad&=\qquad\vdots \\ 2^{53}+12 = 9007199254741004 &= 2^2\times 967\times 3967\times 4547\times 129097, \\ 2^{53}+13 = 9007199254741005 &= 3^3\times 5\times 47\times 56311\times 25209539. \end{aligned} \]

\(2^{53}+12\) と \(2^{53}+13\) について考えます。

たとえば、

\[ \begin{aligned} 2^{53}+13 &= 9007199254741005 = 13233085 \times 680657553, \\ 2^{53}+12 &= 9007199254741004 = 72151796 \times 124836799 \end{aligned} \]

と表すことができます。これらはどちらも \(2^{53}+12\) に丸められます。

あるいは、\((F_0, F_1, \dots, F_n, \dots) = (0, 1, \dots, F_{n-2}+F_{n-1}, \dots)\) として定義される Fibonacci 数列を考えます。 \(i\ge 0\) に対して \((a, b, c, d) = (F_{i+3}, F_{i+2}, F_{i+1}, F_{i})\) とすると \(ad-bc=1\) が成り立つことに注意します。たとえば、下記が挙げられます。

\[ \begin{aligned} F_{39}\cdot F_{42} &= 16944503814015856 = 63245986 \times 267914296, \\ F_{40}\cdot F_{41} &= 16944503814015855 = 102334155 \times 165580141. \end{aligned} \]

参考: https://twitter.com/hidesugar2/status/1675159322886828033（SB 木というのは Stern–Brocot tree を指しています）

ケースとしては次のようになります。

2
13233085 124836799
72151796 680657553

2
63245986 165580141
102334155 267914296

こちらの式を Decimal や long double で計算する場合、\(a\otimes d\) や \(b\otimes c\) などで誤差を出させることができないため、落とせないと思われます。

---

浮動小数点型は（特に初心者にとっては）非自明な挙動をすることが多いです。数学的な誤差評価や、誤差の出るケースの構築について学んでおくと、他の競技者と差をつけやすいかもしれません。

よく言われるデバッグ方法の「ランダムケースを生成し、愚直な解法と突き合わせる」も機能しないことが多いです。ランダムケースでは（運よく？悪く？）誤差が出ない場合が多く、そもそも愚直な解法として誤差が出ない方法を作れるならそれを提出してしまえばいいことも多いですね。

以前書いた記事：https://rsk0315.hatenablog.com/entry/2024/02/25/231237

Twitter でしばしば見かける「どういうケースで WA になるのか教えてください」に対して、実際のケースを提示するだけでは成長に繋がらないと思っているので、構築の仕方も含めて記載しました。 自分の力でそうしたケースを考えられるようになることが肝要だと考えています。