C - Multiplication 3（ABC169復習）

5月31日に開催されたAtCoder Beginner Contest 169。

簡単そうなだと思って提出しまくったがACできなかったC問題を考える。

各問題の制約や入力・出力例はリンク先（AtCoderのサイト）へ。

問題文
A × B の小数点以下を切り捨て、結果を整数として出力してください。
（Aは整数、Bは小数第2位まで与えられる）

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

C - Multiplication 3

a, b = gets.split.map(&:to_f)
puts (a * b).to_i

結果：WA（不正解）実行時間：57 ms

最初簡単すぎてびっくりした。テストはパスするも、提出するとWA（不正解）。

理由を探るために、pメソッドを使いまくる。

標準入力値：1000000000000000 9.99

a, b = gets.split.map(&:to_f)
p a #=> 1.0e+15
p b #=> 9.99
p a * b #=> 9.99e+15
p (a * b).to_i #=> 9990000000000000

変な文字が出ている。小数は見た目と実際が違うってなんか聞いたことがある。

e+15ってエクセルでも見かけたことのある表示。桁数が多すぎるときに出るやつだ。

その後、自分なりに書いたコード。

a, b = gets.split
a = a.to_i
b = b.split(".").map(&:to_i)
bbb = b[0] * 100 + b[1]
puts a * bbb / 100

実行時間：56 ms

b をそのまま計算するのは諦めて、整数部分と小数部分に分け、b を100倍した整数（bbb）と a を掛けて 100 で割る。

これなら有理数を知らなくても解ける。

こっちの方がスマート。

a, b = gets.split
b.gsub!('.', '')  #  '.'を''で置き換えて小数点を消しちゃう
p a.to_i * b.to_i / 100

.gsub("置換元の文字列", "置換後の文字列")は文字列を置き換えるメソッド（由来はglobal substitute）。

bigdecimalライブラリを使う方法。

require 'bigdecimal'

a, b = gets.split
puts (a.to_i * BigDecimal(b)).floor

自分が書きたかったのはこれ。

a, b = gets.split
puts (a.to_i * b.to_r).to_i

to_rは、有理数（Rational）に変換するメソッド。

これのこと。0.1 × 0.1 = 0.01 になるはずだが…

p 0.1 * 0.1
#=> 0.010000000000000002

コンピュータの内部では2進数で計算していることが原因らしく、Rubyに限らず発生する。

最初のWAコードは、丸め誤差が発生したせいで桁数が多すぎてe+15が出てしまった。e+15は、10**15（10の15乗）という意味。

たとえば下のように小数点以下16桁以上ある数は四捨五入されているように見えるが、循環小数などになるとe+15になってしまうのか？すぐにはわからなかったのでまた調べたい。（知ってる方がいたら教えてください）

n = 1.12345678901234567890
p n #=> 1.1234567890123457

正しく計算するためには、有理数を使う。有理数とは分数で表せる（0や整数も含む）数値のことで、コンピュータでも扱うことができる。

Rubyでは、rをつけると有理数（Rational）クラスを使うことができる。

p 0.1r * 0.1r
#=> (1/100)
p (0.1r * 0.1r).to_f
#=> 0.01

いい勉強になった。

次こういう問題が出たら解けるようにする。