「絶対・相対誤差10^(-n)以下であれば正答とみなされる」の意味
yukicoderで以下の問題を解いていて、一つ疑問に思ったので記事にすることにした。
No.379 五円硬貨 - yukicoder
問題文には「相対誤差または絶対誤差が10^(-12)以下であれば正答と見なされる」と書いてある。
このとき、解答では小数点以下何桁まで出力するべきなのか。
10^(-12)は「0.000000000001」と表される。絶対誤差あるいは相対誤差がこの値よりも小さければよい、ということなのだが、そもそも絶対誤差と相対誤差が分からない。そこで少し調べてみた。
・絶対誤差は単純に二つの値の差。
・相対誤差は絶対誤差を理論値で割ったもの。
例えば、100と出力しなければならない問題に、101と出力したときの絶対誤差と相対誤差はどれだけかというと
絶対誤差:101-100=1
相対誤差:(101-100)/100=0.01
となる。ここで注意すべきなのが、絶対誤差は二つの値と単位を同じくするので比較できるが(101kgと100kgの絶対誤差は1kg)、相対誤差は見ての通り比率なので単純に比較はできないということだ。
とりあえず、相対誤差はなんだか面倒くさそうなので、絶対誤差で考えることにする。
10^(-12)は「0.000000000001」だ。小数点以下の桁数は12桁。絶対誤差をこれ以下に抑えるためには、13桁まで出力してやればいいはず。
BigDecimalを使ってdivide(bd,13,RoundingMode.HALF_UP)と計算し、小数点14桁目を切り上げて小数点以下13桁まで出力した。すると無事にAC。
ここで注目したいのが、サンプル2の出力。「335030261.51740766171」となっている。小数点以下は11桁。あれッ、これでは通らないのではないのか。だがよくよく考えてみると、問題文では「絶対誤差あるいは相対誤差」となっているのだから、つまり、この出力の絶対誤差は10^(-12)以上ではあるが、相対誤差が10^(-12)以下となっているため正答、ということなのだろう。このあと自分でも小数点以下の桁数を10桁まで少なくして提出してみたところ、やはり通った。ちなみに9桁まで減らすと通らない。
と、ここまで長々と書いてきたが、結論としては
・「絶対・相対誤差10^(-n)以下」と指定された場合は「小数点以下n+1桁目」まで出力すればよい
ということになる。