part 1 以降があるかはわかりません。

導入？

競プロで、「絶対誤差または相対誤差が \(10^{-6}\) 以下ならば正解と判定される」といった文言はちょくちょく見かけます。

思い出すシリーズ

\(2e-3\) atcoder.jp

思ひでポロポロ pic.twitter.com/64N0Qk3SbX
— きゅうり (@kyuridenamida) 2020年5月1日

その昔、これに対して NaN と出力するだけで AC になるなどの脆弱性もありました。

atcoder.jp

最近の問題のジャッジではそうしたことは起こらないはずです。

atcoder.jp

自前で書くとそういう脆弱性を入れがちなので、testlib とかのライブラリなどを適切に使うとよいと思います。普段 contestant として「お行儀のよい」入力に慣れがちな競プロ er は、そうした脆弱性に疎いんじゃないかな？という気がしています（偏見）。

rian.hatenablog.jp

本題？

contestant 的には、たとえば答えが 1.5 のときに 1.50 とか 1.50000000000000000 とか 1.4999999999999999 とかを出力しても WA になってほしくないですよね。あるいは、指数表記を許すと言われているジャッジであれば、15e-1 とか 150000000000000000000e-20 とか 0.000000000149999999999999e+10 とかを出力しても許されたいわけです。

ということで、ジャッジちゃんと遊びました。

1.5000...00 の形式 atcoder.jp

15000...00e-xx の形式 atcoder.jp

0.000...0015e+xx の形式 atcoder.jp

どれも AC になってくれて、えらいなと思いました。\(2^{27}\) 文字出力しています*1。これを超えると OLE です。

話題 1

環境によっては、指数部が大きすぎると、無限精度で行った場合と異なる結果が返ってきそうです。実数を入力として受け取り、double としてパースし、それを出力するプログラムを考えます。

#include <cstdio>
int main() {
  double x;
  scanf("%lf", &x);
  printf("%f\n", x);
}

これに対して、2000...00e-xx の形式で、2.0 と等しいはずの値を与えてみます。

% echo 20.0e-1 | ./a.out
2.000000

% (e=19999; printf 2; repeat $e printf 0; echo e-$e) | ./a.out
2.000000

% (e=20000; printf 2; repeat $e printf 0; echo e-$e) | ./a.out
20.000000

% (e=20306; printf 2; repeat $e printf 0; echo e-$e) | ./a.out
19999999999999999720621195205129155434005283676252727750499321471767131705345487698129692828457921333572758560785309230786706345700504206672551904741230794021461383329378750357138079702146292679283246532142253440022040339106608037192915625377123894402342976922345843644278133859702564244005353335500042141696.000000

% (e=20307; printf 2; repeat $e printf 0; echo e-$e) | ./a.out
inf

わーびっくり。AtCoder のコードテストの環境では再現しませんでした。処理系によるのかな？

Because computers are finite, C++ implementations are inevitably limited in the size of the programs they can successfully process.

と規格にも書かれているし、そういうのも許されているのかもしれません？上記は入力側じゃなくてプログラム側の話な気もするので、やっぱり許されてないかもしれません？

ソースコード中にそうしたリテラルを書いた場合はちゃんと出力してくれました。

% cat <<EOF | g++-10 -xc++ - -O9 -o fl && ./fl
cmdand heredoc> #include <cstdio>
cmdand heredoc> int main() {
cmdand heredoc>   double x = $(e=100000; printf 2; repeat $e printf 0; echo e-$e);
cmdand heredoc>   printf("%f\\n", x);
cmdand heredoc> }
cmdand heredoc> EOF
2.000000

（cmdand heredoc> もプロンプトですが、syntax highlighting がこわれてしまった）

話題 2

ちなみに、浮動小数点数には 16 進のリテラルもあって、0xH.HHHp+D の形式です。H の部分を 16 進数で書き、D にはビットシフトの幅を書きます。たとえば、\(2.75 = (2^3+2^1+2^0)/2^{-2}\) なので、2.75 の代わりに 0xbp-3 や 0.x1.6p+1 などと書けます。

printf("%a\n", x) などとすればこの形式で出力できますが、ジャッジはこの形式には対応していないようでした（かなしいね*2）。

atcoder.jp

おわり

今回は ABC 130 C のジャッジちゃんと遊びましたが、別のジャッジちゃんは別の挙動をするかもしれません。誤差まわりについても遊んでみたいかもしれませんね。

*1:出力内容によっては 1 文字少ないかもです。

*2:別にかなしくはなくない？

えびちゃんの日記

えびちゃん（競プロ）の日記です。

誤差許容ジャッジちゃんと遊んでみる (part 0)

導入？

本題？

話題 1

話題 2

おわり