C - Sqrt Inequality Editorial by rsk0315

Python の Decimal による素朴な解法が嘘である話

Python の次のような解法が通ります。

from decimal import Decimal
a, b, c = map(Decimal, input().split())
print("Yes" if a.sqrt() + b.sqrt() < c.sqrt() else "No")

これによって、初心者が「誤差に関する問題であるが、Decimal を使って高い精度で計算することで正しく判定できる」と思い込んでいるのをしばしば見かけますが、この解法では正しく判定できないケースが存在します。

撃墜ケース

2 8 18

a.sqrt() などの各値は次のようになっています。丸めを行う際に誤差が発生します。

1.414213562373095048801688724 ← √a
2.828427124746190097603377448 ← √b
4.242640687119285146405066172 ← √a + √b
4.242640687119285146405066173 ← √c

これを見てわかるように、\(\sqrt{2}+\sqrt{8}\lt\sqrt{18}\) と判定してしまいます。 もちろん、実際には \[\sqrt{2}+\sqrt{8} = \sqrt{2}+2\sqrt{2} = 3\sqrt{2} = \sqrt{18}\] なので、これは正しくありません。


また、次のようにすることで精度を上げたり下げたりすることができます(精度を上げると計算量は増えます)。

from decimal import getcontext
getcontext().prec = 400  # 任意に設定

デフォルトでは 28 になっています (ref)。

これによって正当な解法にできると思う人がいるかもしれませんが、もちろん不当です。 丸めによって生じる誤差は、桁数を上げても回避できるわけではないためです。

丸め方向はいくつか用意されており、

getcontext().rounding = 'ROUND_HALF_EVEN'

などで指定できます (ref)。デフォルトは ROUND_HALF_EVEN です (ref)。

実際に、各丸め方向 (ROUND_CEILING, ROUND_DOWN, ROUND_FLOOR, ROUND_HALF_DOWN, ROUND_HALF_EVEN, ROUND_HALF_UP, ROUND_UP, ROUND_05UP) について、prec を 1000 以下(デフォルトである ROUND_HALF_EVEN については 3000 以下)の各正整数に設定した場合に、制約の範囲内で撃墜ケースが存在することを確認しました。

大半は、(2, 2, 8), (8, 8, 32), (2, 8, 18) のような小さいケースでも撃墜できました。


精度を十分高くした上で、c.sqrt() - (a.sqrt() + b.sqrt()) の絶対値が十分小さければ、などで判定するのはどうでしょうか?「十分」というのがどの程度なのかをきちんと理解した上であれば大丈夫でしょう。

理解せずに「だいたい 1e-20 とかでやっておけばいいだろう」のような態度で臨むのはあまりおすすめしません。

posted:
last update: