ABC169に参加してみた

初めに

ABC169に参加しました。いや~過去最高にWA出しましたね(笑)
やっていて辛くなりました、、、B、Cでやられました、、、
Bはオーバーフローさせないようにすれば良いことは分かったんですが、実装が出来ませんでした。
Cも誤差の影響でWAしてるってことはわかったんですが、実装が出来ませんでした。
B問題についてはケアレスミスで実装に失敗していただけだったので、
今回はC問題についてのみ書いて行こうと思います。(浮動小数点数のおさらいもしたいので)

https://atcoder.jp/contests/abc169

※ブログ内で問題の制約事項をすべて記載はしないので、制約事項は↑のURLより参照願います。

C - Multiplication 3

浮動小数点数とはなんぞや

まず問題の話に入る前に、この問題のきもとなる浮動小数点数とはなんぞやって話ですが
端的に言うと小数点を固定せずに表現された数です。(対義後は固定小数点数)

浮動小数点数は小数点が固定出ないため表現が無数に存在します。
表現の形式が統一されていないと計算等に不便なため、
コンピューターで使う浮動小数点数の表現形式は一般的に
IEEE754標準で決められた形式が使用されます。

表記例は以下のようになり、それぞれの箇所に名称がついています。

  1.1 × 2^ 8

  1.1 → 仮数
  2 → 基数
  8 → 指数

double型の場合は以下のような式であらわされ、内部構造は下記イメージのようになっています。
仮数部については、「1.・・・」というように表現するよう決められているため、
先頭の1以降の数字が変数に格納されます。

  (-1)符号部 × 2指数部-1023×(1.仮数部)

f:id:hgm_blog:20200607160115j:plain
イメージ

式の(指数部-1023)の箇所で記載されている「1023」はバイアス値と呼ばれており、
バイアス値のおかげで指数がマイナスの場合も符号や2の補数表現を使わずに指数を表せます。

例)1.1 × 2-2 の場合

  (-1)符号部 × 2指数部-1023×(1.仮数部) = (-1)0 × 21021-1023×(1.1)
                    = (-1)0 × 2-2×(1.1)
                    = 1.1 × 2-2

※詳しくは下記のサイトの説明や表がわかりやすかったので参照してみて下さい。

ss.sguc.ac.jp

ここで、浮動小数点数を使う点で注意が必要なのが誤差です。
例えば10進数の0.1を2進数で表現すると以下のように循環小数であらわされる場合があります。
(同じ数字だけが繰り返し現れる小数を循環小数といいます)

  0.1(10進数) = 0.000110011001100…(2進数)

コンピュータ内部では有限桁しか扱えないため、どこかで打ち切る必要があり、
それにより真の値との誤差が生じてしまいます。(他の誤差については下記サイトを参照してみて下さい)
※因みに10進数の1.5や1.75のように正確に表現出来る数もあります。

  1.5 → 21+2-1   1.75 → 21 + 2 ^(-1) + 2-2

https://it-lab.com/column/floating-point-number/

解説を見てからの回答
#include<bits/stdc++.h>

using namespace std;
using ll = long long;

const long long INF = 1LL<<60;

int main(){

double B;

ll LB,A,ans;

cin >> A >> B;

LB = ll(B*100 + 0.1);

//LB = lround(B*100 + 0.1);

ans = A*LB;

ans /= 100;

cout << ans << endl;

return 0;

}   

それでは、ようやく問題の話になりますがこの問題は
整数Aと小数2桁まで与えられるBの掛け算の結果を出力する問題です。

AとBの入力の条件についてですが、以下のようになっています。

  0 \leq A \leq 10^{15}
  0 \leq B \leq 10
 Aは整数
 Bは小数点第2位まで与えられる

最初は、double型でAとBを計算してA×Bの計算をしたのですが、 double型で扱えるのは10進数で約15桁なので、精度(有効数字)が足りないため正確な計算が行えません。

そこで、「Bに100をかけ整数同士の掛け算を行えば誤差を考えずに計算が行えるはず!」
となるかもしれませんが、この計算でも誤差が発生する可能性があります。

前述で記載したように小数部分を2進数の有限桁数で表現出来無いようなケースの場合、
掛け算した結果が本来の値より大きい場合や小さくなる場合があります。(以下は例です。)

f:id:hgm_blog:20200607184405j:plain
イメージ

小さくなった場合は、C++の整数型に代入した場合は小数点以下が切り捨てられてしまうため、
間違った計算が行われてしまいます。

そこで、プログラムではB*100.0の計算結果は正しい値に近いはずなので、
本来の値より値が小さかった場合を考え、0.5を足してから
整数型にキャストを行いA×Bの計算を行っています。

こうすることで、整数型での計算に落とし込めるため、正しい答えを出力することが可能です。

他の解法については、浮動小数点数オタクさんの記事でわかりやすく記載されているので、
そちらを参照してみて下さい!

浮動小数点数オタクが AtCoder Beginner Contest 169 のC問題をガチで解説してみる - Qiita

最後に

今まではあまり誤差を意識せずにdouble型を使用していましたが、今回のブログを書くにあたり
色々調べるうちに「浮動小数点数こわい( ;∀;)」ってなりました。(笑)
と、同時にブログを書くと色々と調べて理解する必要が出てくるので、
お勉強には丁度良いかなぁと改めて思いました。(後で見返せますしね)