[Python]演算誤差 ARC109B

ARC109B

長さ n+1 の丸太を買って、短い方から丸太を作れるだけ作った後、残りの丸太を買うのが最適です。この「作れるだけ作った」ときにいくつの丸太が作れるかを求めるためには、$1 + \dots + k \leq n+1$ を満たす最大の整数 k を求めれば良いです。

私は、$1 + \dots + k = k(1+k)/2$ であることを使って、 $k(1+k)/2 \leq n+1$ を満たす最大の $k = \frac{-1+\sqrt{8n+9}}{2}$ を実装し提出しましたが、ルート演算誤差のために1ケースWAでした。本問の内容であれば、10進数の小数型Decimalを用いることで対応可能だと思われます。

サンプルコード

from decimal import Decimal

n = int(input())

k = int((-1 + Decimal(8*n+9)**Decimal(0.5))/2)

print(n-k+1)

誤差を確実に回避するために、二分探索をすることで求めることができます。