AtCoder ARC094 D問題
解き方は正しかったのですが、long doubleの可能性に思い当たらなかったためにWAし続けたのでメモ。WAになったのは次の2つが原因です。
1. sqrt関数にdouble型の引数を渡した
この問題では最大10の18乗の平方根を取る必要があります。平方根を算出する関数sqrtは浮動小数点を引数としています。この際、floatやdoubleで値を渡すと情報落ちが発生して正しい解が得られない場合があります。
doubleの仮数部は52bitなので約4.5×10^15までしか正確に表現できないのが原因です。
倍精度浮動小数点数 - Wikipedia
10^18を浮動小数点で正確に表現するにはlong doubleを用います。long doubleは仮数部が64bitなので約1.8×10^19まで正確に表現可能です。
2. cmathをincludeしていなかった または sqrtl関数を使用しなかった
long doubleの平方根を得るためには次の2つの方法があります。
- math.hのsqrtl関数を用いる
- cmathのsqrt関数にlong doubleを渡す
math.hのsqrt関数を使用すると、引数がdoubleにキャストされてしまいます。math.hにはsqrtlという別の名前の関数がlong double用に用意されているのでそちらを使います。
またcmathのsqrt関数を用いる方法もあります。C++では関数がオーバーロードできる（引数が異なる同名の関数を作れる）ようになったので、cmathの平方根を求める関数はsqrtという名前に統一されています。long doubleを明示的に渡すことにより、long double版のsqrt関数を使うことができます。
Ex. bits/stdc++.h
沢山includeを並べている解答例をよく見る中、次の一行だけincludeしている解答例を見かけました。
#include <bits/stdc++.h>
標準ライブラリを全部includeしてくれます。今回必要だったcmathも含まれています。AtCoderでは使えるようなので、次回からはこれを使おうと思います。
