AtCoder Beginner Contest 169 C を Python で

こんにちは，タムログです。今回は結構問題になった昨日の ABC169C の問題の解説をしていきたいと思います。自分もただ掛け算を出力するだけなのに全然 AC にならなくて，発狂しかけました。先に言っておくと小数の演算には要注意ということですね。勉強になりました。
それでは，早速行きましょう。まずは問題文から。

C – Multiplication 3

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 300 点

問題文

A×B の小数点以下を切り捨て、結果を整数として出力してください。

制約

0≤A≤10^15
0≤B<10
A は整数
B は小数第 2 位まで与えられる

入力

入力は以下の形式で標準入力から与えられる。

A B

出力

答えを整数として出力せよ。

入力例 1

198 1.10

出力例 1

217

198×1.10=217.8 なので、小数点以下を切り捨てて答えは 217 となります。

入力例 2

1 0.01

出力例 2

入力例 3

1000000000000000 9.99

出力例 3

9990000000000000

解説

はい，この問題「やるだけ」じゃないんですよね。ただ単純に積の値を出力してしまうと，WA 連発してしまいます。
なぜこのようなことになってしまうかというと，コンピュータの数の表現の仕方に原因があります。

私たちは普段１０進数で数を表現していますが，コンピュータでは2進数で数を表現しています。これが原因で丸め誤差と言うものが生じてしまいます。簡単に言うと，普段使っている数をコンピュータ内部で正確に表現することができないわけです。例を挙げてみましょう。パソコンにもよるかもしれませんが，1.1 + 2.2 の計算結果を出力してみましょう。

>>> 1.1 + 2.2
3.3000000000000003

このように，本来 1.1 + 2.2 = 3.3 であるはずなのに，上記の結果は微小な誤差が生じていますよね？
こういう小さな誤差のせいで得たい出力結果が得られなくなっているのです。

この問題を解消するための手法の一つは，整数に直して計算することです。整数であれば2進数で正確に表現することができますから，このような誤差を考えなくてすみます。今回の問題設定では，b は小数第二位まで与えられるとありますので，十進数的考え方なら１００倍してやれば整数になります。

ただ，ここにも罠があります。十進数では小数第二位までであっても，二進数で表すと無限小数になってしまうことがよくあり，このせいで丸め誤差が生じるということを説明しました。これより，ただ１００倍してやるだけでは，十進数では整数に見えても二進数ではまだ小数部分が残っている場合があります。この時，この小数部分が悪さをして，結果的におかしな値になってしまうことがあるのです。これは非常に稀なケースだと思うのですが，この問題ではちゃんとこのケースをはじくようなテストケースが与えられているようです。
つまり，整数の計算なら丸め誤差が生じないから，整数に直して計算しようとするが，コンピュータ内部で入力値が既に誤差を持っている場合，単純に１００倍したところで整数に戻らないわけです。

例えば，0.6 という数字を考えましょう。これは2進数では扱えない数ですから，コンピュータ内部では 0.5976・・・という値になっています。これをただ100倍しただけでは597.6・・・と，やはり小数部分が残ってしまいますよね。

この問題を解決する方法は色々あると思いますが，ここでは2種類紹介します。

解法１

一つ目は，数字を文字列として受け取った後に，小数を表す " . " を消すことで，10進法的に100倍するという考え方です。先ほどの 0.6 の例で行くと，

0.60 を文字列として受け取る → b = “0.60"
" . " を消す → b = " 060 “
int 型に直す → b = 60 ※百倍になっている

このようにすれば，十進数的に100倍したことになります。

Pythonでの実装方法は，まず a,b を文字列として受け取った後に，a はそのまま int 型にして，b は replace(“.", " “)の作業をした後に int 型にします。これは b の文字列の中の “." を，何もないという意味の " " に置き換えている（"."を削除している) ということになります。これで a*b をした後に 100 で割った商を出してあげれば，得たい出力が得られます。これが解答例１です。

解答例１

a, b = input().split()

a = int(a)
b = int(b.replace(".", ""))

c = a*b // 100

print(c)

解法２

2つ目の解法は，Python ならではのものです。それは decimal モジュールを用いるというものです。これは，先ほどから述べている2進数表現による丸め誤差を無くすためのもので，10進数表現で厳密な計算ができるというものです。10進数の厳密な計算を行いたい場合にはこれを用いればいいので，これからこういう系統の問題を解く時にはこの Decimal モジュールを使えばいいのではないでしょうか。こちらのほうが解法1よりも汎用性が高くてお勧めです。使い方は次の通りです。

from decimal import Decimal

これでインポートした後に，文字列を使って十進数表現にします。具体的には，例えば 412 と 3.14 の計算を厳密に行いたい場合には，

a = "412" //文字列
b = "3.14" //文字列
dec_a = Decimal(a)
dec_b = Decimal(b)

print(a*b)

このように記述します。

上記のように10進数表現ができるので，あとは丸め誤差を恐れずに入力値 a と b の積を計算してやり，結果を int 型に直して出力してやりましょう。int 型に直すときには小数点以下は全て切り捨ててくれるので，今回の問題設定では単純に積を int 型に直して出力してやるだけで大丈夫です。

これが，次の解答例２です。

解答例２

from decimal import Decimal
a, b = input().split()

dec_a = Decimal(a)
dec_b = Decimal(b)

print(int(a*b))

いかがだったでしょうか。
小数の計算が怖いものだととても実感させてくれた非常に良い問題だったかと思います。これからは Python では decimal モジュールを使えばよさそうですね。何か悪い点があるのでしょうか。詳しい方，ぜひ twitter で教えてください。

少しでも参考になれば，twitter のフォロー，RT よろしくお願いします。
それでは！