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

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

AtCoder ABC 169 C - Multiplication 3 (茶色, 300 点)

AtCoder AtCoder300点 ABC-C 誤差 コーナーケース 茶色diff マルチテストケース問題 入力が定数個

誤差は怖い！！！！！！！

問題へのリンク

問題概要

整数 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;
}