ABC139のD問題をPythonで解いたときにハマったやつ

備忘録です。

まずは誤答例のソースコード

#WA
N = int(input())

print(int(N*(N-1)/2))

次に正答例のソースコード

#AC
N = int(input())

print(N*(N-1)//2)

はい？なにが違うの？？

種明かし

誤答例だと一度浮動小数点数を経由しているのがまずいです。どういうことかわかりやすく示したのが次のコード。

ans = 0
for i in range(1,20):
    print(float(ans))
    ans*=10
    ans += i%10

出力結果

0.0
1.0
12.0
123.0
1234.0
12345.0
123456.0
1234567.0
12345678.0
123456789.0
1234567890.0
12345678901.0
123456789012.0
1234567890123.0
12345678901234.0
123456789012345.0
1234567890123456.0
1.2345678901234568e+16
1.2345678901234568e+17

このように、保持可能な仮数より大きな仮数は丸められてしまうわけです。元の問題に戻ると、Nが大きすぎる(例えばN=999999999)場合には誤差が生じてしまうということです。実際に実行してみると以下のようになります。

#N=999999999
N = int(input())
print("N1 =",int(N*(N-1)/2))
print("N2 =",N*(N-1)//2)

出力結果

N1 = 499999998500000000
N2 = 499999998500000001

型が自動的にキャストされるのは便利ですが、バグの原因にもなる得るということでしょうか...。