ABC191 D問題のコードのTLE発生原因について

Question

Atcoder Beginner Contestにおいて以下のようなコードを提出たところTLEになりました。
for文が一つのため最大でも4*10^5で10^6以下に収まっているためなぜTLEとなってしまったのかが理解できません。

型変換やDecimalの計算にはかなりの時間を要するのでしょうか。
なぜTLEが起きてしまったのか、コードを改善するとしたらどこなのかご教授いただければと思います。

※Decimalを使わずfloat型で提出したところWAになりました。おそらく誤差が出てしまったものと思います。

from decimal import Decimal
import math

x,y,r = map(float,input().split())
ans = 0
i_min,i_max = math.ceil(x-r),math.floor(x+r)

for i in range(i_min,i_max+1):
  y_max = y + float((Decimal(str(r**2-(i-x)**2)))**(Decimal("0.5")))
  y_min = -y_max + 2*y

  ans +=(math.floor(y_max)-math.ceil(y_min)+1)
  
print(ans)

Answer 1

どの程度の改善が必要かわかりませんが、一番時間を食ってるのは平方根の計算だと思うので、そこをsqrt()でやるとそれだけで相当な高速化にはなります。

Comments

[inoino]

回答ありがとうございました。
想定解は10^4を掛けて精度を維持するものでした。