【Python】ABC191 D - Circle Lattice Points (誤差問題)【AtCoder】

ABC191 D - Circle Lattice Points

ふりかえりをしていたが、
解説見て、解き方わかったのにどうしてもWAが消えない
10000倍して、整数でやってるつもりなのに、どうして！！！
ということでACの人たちのコードみたら、
10000倍してる人もルート計算で結局Decimal使ってるっぽい！

結論

Decimal最強伝説！
誤差問題はDecimalで提出しましょう。
※ちなみに、PyPyはDecimal計算遅いので、Pythonで提出しましょう。

以下結論までの軌跡・・・

提出したコードたちはこちら

WA1.py

import math,sys
def LS(): return list(sys.stdin.readline().rstrip().split())
#############################
from decimal import Decimal
n = 10000
X,Y,R = [int(Decimal(x)*n) for x in LS()]

ans = 0
for y in range(math.ceil((Y-R)/n),math.floor((Y+R)/n)+1):
    z = (R**2-(Y-y*n)**2)**0.5
    ans += math.floor((X+z)/n)-math.ceil((X-z)/n)+1

print(ans)

ansの足し算のところで、整数+小数だから、そこで誤差発生してるのかな？
zを整数にしてみよう。

WA２.py

import math,sys
def LS(): return list(sys.stdin.readline().rstrip().split())
#############################
from decimal import Decimal
n = 10000
X,Y,R = [int(Decimal(x)*n) for x in LS()]

ans = 0
for y in range(math.ceil((Y-R)/n),math.floor((Y+R)/n)+1):
    z = int((R**2-(Y-y*n)**2)**0.5)
    ans += math.floor((X+z)/n)-math.ceil((X-z)/n)+1

print(ans)

なんでや・・・

原因は「**0.5」

ルートを出すときに、0.5っていうfloat型使ってるんじゃい！！！
誤差がでるんじゃい！！！
無意識だった。。。

AC1.py

import math,sys
def LS(): return list(sys.stdin.readline().rstrip().split())
#############################
from decimal import Decimal
n = 10000
X,Y,R = [int(Decimal(x)*n) for x in LS()]

ans = 0
for y in range(math.ceil((Y-R)/n),math.floor((Y+R)/n)+1):
    z = int(Decimal(R**2-(Y-y*n)**2).sqrt())
    ans += math.floor((X+z)/n)-math.ceil((X-z)/n)+1

print(ans)

というかそもそも誤差問題全部Decimalで計算すれば最強じゃね？
10000とかかける必要なくね？？？

AC2.py

import math,sys
def LS(): return list(sys.stdin.readline().rstrip().split())
#############################
from decimal import Decimal
X,Y,R = [Decimal(x) for x in LS()]

ans = 0
for y in range(math.ceil(Y-R),math.floor(Y+R)+1):
    z = (R**2-(Y-y)**2).sqrt()
    ans += math.floor(X+z)-math.ceil(X-z)+1

print(ans)

まとめ

Decimal最強伝説！
誤差問題はDecimalで提出しましょう!!!

おわり！！！