けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 169 C - Multiplication 3 (300 点)

誤差は怖い!!!!!!!

問題へのリンク

問題概要

整数  A と、"x.yz" のフォーマットで与えられる実数  B が与えられる。
 A \times B の小数点以下を切り捨て、結果を整数として出力せよ。

制約

  •  0 \le A \le 10^{15}

考えたこと

数値誤差が怖いというテーマの問題は、パナソニックコンでもあった。かの有名な「 \sqrt{a} + \sqrt{b} \lt \sqrt{c} ですか?」という問題!!!

atcoder.jp

今回も数値誤差が怖くて、たとえば次のようなコードだと、WA になってしまう。

int main() {
    long long A;
    double B;
    cin >> A >> B;
    cout << (long long)(A * B) << endl;
}

このようになってしまう原因は、「double 型には 15〜16 桁程度の精度しかない」というところにある。今回、

  •  A の有効数字は 15 桁
  •  B の有効数字は 3 桁

なので、 A \times B の計算には、18 桁程度の有効数字が欲しいのだ。double 型では足りない。

考えられる対策としては、

  1. double 型より精度の高い型を用いる
  2. 整数計算で済ませる

が挙げられる。

解法 (1): long double 型を使う

long double 型ならば、処理系依存ではあるが、double 型の倍の精度を出すことができるので、それで一応通る。

なお、得られた long double 型の値を単純に long long 型にキャストするのでは、88888.00 といった値が内部的には 88887.99999999 のように扱われて 88887 になったりするのが怖い。なので、0.001 といった微小な値を足しておく必要がある (今回は、微小値を足す処理をしなくても通ったが、それはテストケースが弱かったためっぽい)。

#include <bits/stdc++.h>
using namespace std;

int main() {
    long double A, B;
    cin >> A >> B;
    cout << (long long)(A * B + 0.001) << endl;
}

補足:数の表現と誤差

驚くべきことに、計算機では 0.1 のような単純な値でさえ正確には表すことができてない。なぜなら、コンピュータ内部では、数値は基本的に二進数で扱う。0.1 を二進法で表すと、

0.000110011001100110011...

という具合に無限小数になるのだ。どこかで区切らないといけないので、誤差が生じてしまう。このような誤差はとても怖い。実は今回の問題でも、たとえ long double 型を使ったとしても、

cout << (long long)(A * B) << endl;

ではダメなケースが存在するようだ。具体的には、

  • A = 100
  • B = 0.53

でダメになる。このケースはテストケースに含まれていなかった模様。なのでやはり

  • EPS = 0.001

といった微小値を用意してあげて、

cout << (long long)(A * B + EPS) << endl;

という風にしてあげる必要がある。

 

解法 (2): 基本的に整数演算で済ませる

基本的には整数演算のみで済ませることができるならば、その方が安心かなと思う。

今回、 B は小数点以下 2 桁までしかないことがわかっている。つまり、 B 100 倍すると整数になるのだ。そのことを利用して、

 A × (100B) /  100

を計算すれば、整数演算のみですべてを済ませることができる! 100B の値の計算は、 B を文字列として受け取るのが明快だと思う。

大きな罠 (100B の計算)

なお、 100B を計算する部分でも大きな罠があって、

  •  B を double 型として受け取る
  • それを 100 倍して long long 型に cast する

という素朴な方法では、実は WA になってしまう!!!!!!!!!

文字列として扱うのが確実だと思われるが、どうしても必要であれば、

long long B100 = (long long)(B * 100 + 0.001);

という具合に、0.001 といった「微小値 EPS」を足してから long long 型にキャストするようにすれば通すことができる。

解答例 2-1: B を文字列として扱う方法

#include <bits/stdc++.h>
using namespace std;

int main() {
    long long A;
    string B;
    cin >> A >> B;
    long long B100 = (B[0]-'0')*100 + (B[2]-'0')*10 + (B[3]-'0');
    cout << A * B100 / 100 << endl;
}

解答例 2-2: 100B に微小値を足す方法

#include <bits/stdc++.h>
using namespace std;

int main() {
    long long A;
    double B;
    cin >> A >> B;
    long long B100 = (long long)(B * 100 + 0.001);
    cout << A * B100 / 100 << endl;
}