はじめに
今回Atcoder Regular Contest のC問題「AtCoDeerくんと選挙速報」を解いてみたのですが、なぜかWAが4回ぐらいでて1時間ぐらい溶かしたので反省文を書きます。
問題と解法について
今回の問題では$\lceil A/x \rceil$と$\lceil T/y \rceil$
(A, T, x, y は整数)を求めることがメインとなるのですが、そのときのこの計算方法が大事になります。
ミスした原因：Ceil関数内の割り算
自分は愚直にpythonのmathモジュールのceil関数を利用して
#ここでの割り算は誤差をうんでしまう
A_div = math.ceil(A/x)
T_div = math.ceil(T/y)
と計算していたのですが、これは良い方法ではありません。
Pythonでは割り算の結果はfloatとなってしまい、floatの数値は16桁ぐらいまでしか精度が保証されていません。
次のブログを参考にさせていただきました。
以下に1を18桁並べた例をあげます。
#正解
111111111111111111 // 9
>>12345679012345679
111111111111111111 / 9
>>1.234567901234568e+16
#間違い
int(111111111111111111 / 9)
>>12345679012345680
ここで商はfloatの17桁のため、16,17桁で狂いが生じてしまっているのがわかります。
これが今回の問題でWAが生じた原因となります。
以下は以前書いていた間違った内容でご指摘を受けて直させていただきました。
なぜなら我々が普通に整数の割り算をするときは
1 / 1 = 1
2 / 1 = 2
100 / 10 = 10
100 / 40 = 2.5
と正確にでますが、コンピュータの世界では少し誤差が生まれます。
それはpythonでformat関数を利用してfloat formatにするとわかります。
pythonで/を使うとfloatとして結果が出力されるため、何度も計算をしていると誤差がceil関数に影響することになり、誤った答えが出てしまいます。詳しいことはドキュメンテーションで確認できます。
https://docs.python.org/3/tutorial/floatingpoint.html
ではどうするべきだったか
誤差を生まないために、以下のように書くべきでした。
#負の数にして//を使えばfloatを経由せずに計算することができる。
A_div = -(-A//x)
T_div = -(-T//y)
負の数にして切り捨て//を用いて、もう一度マイナスをかければintを使っているためfloatによる計算結果の誤差を産むことはありません。これによってceilを再現することができます。
7と5を利用すると
$\lceil 7/5 \rceil$ = $\lceil 1.4 \rceil$ = 2
-(-7 // 5) = -(-2) = 2
と同じ結果が生まれます。
最後に
Ceil関数は便利ですが、中身の割り算には気をつけましょう。
以上です。