競プロをはじめた家事手伝いロボットのブログ

競技プログラミングをしている家事手伝いロボットのブログです

誤差ジャッジ問題のw/t作業をするときのためのTIPS

お気持ち表明です(?)

これはなに

浮動小数点数を扱うのは人間には難しいことが知られていますが、競技プログラミング界では浮動小数点数が必要になる(ほんとうに？)問題が頻繁に出題されています。
みなさんも writer/tester 作業をしたくなるときがありますね。たまには実数で出力をさせる問題が書きたくなるときがありますね(ありますか？)。具体的にはこんなときですね。

  • 幾何などで、答えが有理数になりそうにない
    • \pi に有理数がかかった形式では \pi で割っておいたり、整数の平方根になる場合は二乗して出力させたり、atcoder.jp のような感じにして有理数にエイヤとしてしまえる場合もあります
  • 答えが有理数になりそうだけど、分母が非常に大きな素因数を持つ場合がある(し、「この素因数は持たない」といえるちょうどいい大きさの素数がない)
  • 答えが有理数になりそうだけど、想定解が二分探索などなのでexactな値を求めさせるのは難しい/できるけど心苦しい
  • なんか mod とって無理矢理整数にするのは嫌

浮動小数点数を扱うのは人間には難しいですが、こういう場合に備えてやっていけることはあります。まとめてみました。

問題文編

実数で出力をする問題では、基本的に正しい値を出力することはできません。

非常に単純な問題設定と非常に単純なコードの組み合わせではじめて正しい答えが出ます。たとえば、

atcoder.jp

に対して、

#include <iostream>

int main(){
  int A, B;
  std::cin >> A >> B;
  std::cout << A * B / 100.0 << std::endl;
  return 0;
}

は正しい答えを出力します。しかし、

#include <iostream>
#include <iomanip>

int main(){
  int A, B;
  std::cin >> A >> B;
  std::cout << std::fixed << std::setprecision(17);
  std::cout << A * B / 100.0 << std::endl;
  return 0;
}

こうすると正しい答えを出力しなくなりますね。

誤差が出てしまう例

もうちょっと複雑な問題になると「正しい値」が10進では無限小数になってしまうこともあり、正しい答えを出力させるのが不可能になることもあります。

このため、実数で答えを出力する問題では問題文に出力に許容する誤差について明記することが慣習となっています1。

「ただし、正しい値からの相対誤差もしくは絶対誤差が10^{-6}以下のとき、正解と判定されます。」

誤差ジャッジ問にはよくこういう文章が 出力 の項に書かれています。基本的に、問題文を書く場合はこのような文を書いておけばいいです（誤差の具体的な値は問題によって変えたほうがいいです）。

「正しい値からの〜のとき、正解と判定されます。」

正しい値を計算するのが難しいことは上で話したので、「じゃあこのジャッジをするのは無理じゃん」となるかもしれません。 実はそうではなくて、これは「〜のとき、正解と判定されます。」の解釈の問題で「そうでないとき100%落とします」とは言っていないことが大事です。 なので、（理想的には） writer/tester は「正しい値と想定解との誤差」を上から評価して、正しい値からの誤差が hoge のとき を完全に含むような想定解との許容誤差を考え、設定することになります。

これを「想定解からの誤差が...」としてしまうとコンテスタントは「writerの想定解が(入力とは関係なく)5000兆を出力するもので、これまで出たそれっぽいACは全て気まぐれで出たACである」のような可能性を排除できませんが、なぜかよく使われている表現です2。

「相対誤差もしくは絶対誤差」

なぜ「相対誤差」と「絶対誤差」のどちらか片方にしないのか？は、浮動小数点数の表現の仕方に理由があります。 ここでは深入りはしませんが（「浮動小数点数」とか「IEEE 754」とかで調べたらすぐ出てきます）、だいたい「大きいところはざっくり、小さいところは細かく、すごく小さいところはほどほどに」という感じです。 なので、大きい値のところは目が粗いので絶対誤差が大きく、すごく小さいところはほどほどなので相対誤差が大きくなってしまいます。

例えば、double で表現できる正の値のうち、小さい方から2つと大きい方から2つ取ってきて相対誤差と絶対誤差を見てみましょう。

小さいほう2つは、こちらです。

0.000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000004940656458412465441765687928682213723650598026143247644255856825006755072702087518652998363616359923797965646954457177309266567103559397963987747960107818781263007131903114045278458171678489821036887186360569987307230500063874091535649843873124733972731696151400317153853980741262385655911710266585566867681870395603106249319452715914924553293054565444011274801297099995419319894090804165633245247571478690147267801593552386115501348035264934720193790268107107491703332226844753335720832431936092382893458368060106011506169809753078342277318329247904982524730776375927247874656084778203734469699533647017972677717585125660551199131504891101451037862738167250955837389733598993664809941164205702637090279242767544565229087538682506419718265533447265625
0.00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000988131291682493088353137585736442744730119605228649528851171365001351014540417503730599672723271984759593129390891435461853313420711879592797549592021563756252601426380622809055691634335697964207377437272113997461446100012774818307129968774624946794546339230280063430770796148252477131182342053317113373536374079120621249863890543182984910658610913088802254960259419999083863978818160833126649049514295738029453560318710477223100269607052986944038758053621421498340666445368950667144166486387218476578691673612021202301233961950615668455463665849580996504946155275185449574931216955640746893939906729403594535543517025132110239826300978220290207572547633450191167477946719798732961988232841140527418055848553508913045817507736501283943653106689453125

ちょうど倍なので、相対誤差は 1 、絶対誤差は 4.94\times 10^{-324} です。

大きいほう2つは、こちらです。

179769313486231570814527423731704356798070567525844996598917476803157260780028538760589558632766878171540458953514382464234321326889464182768467546703537516986049910576551282076245490090389328944075868508455133942304583236903222948165808559332123348274797826204144723168738177180919299881250404026184124858368
179769313486231550856124328384506240234343437157459335924404872448581845754556114388470639943126220321960804027157371570809852884964511743044087662767600909594331927728237078876188760579532563768698654064825262115771015791463983014857704008123419459386245141723703148097529108423358883457665451722744025579520

相対誤差は 1.11\times 10^{-16} 、絶対誤差は 2.00\times 10^{292} です。

これははしっこのほうを取ってきているので誇張されたといえる例ですが、値が非常に狭い範囲を取るなどでなければ「相対誤差もしくは絶対誤差」のような形にするといいと思います。

atcoder.jp

これは出力がすべて \lbrack0,3\rbrack に収まるので絶対誤差だけでジャッジしている例です。

10^{-6}

上の例でも相対誤差/絶対誤差のどちらかは 10^{-15} より小さかったように、「真の値に最も近い、double で表現できる値」を取ってくることができれば、その相対誤差もしくは絶対誤差はだいたい 10^{-16} 程度に収まります。 なのに許容誤差を 10^{-6} などにするのはなぜかというと、浮動小数点数を用いた四則演算などでは（ほぼ）毎回誤差が生じるためです。

計算が増えれば増えるほど誤差の絶対値の期待値は増えていきがちです。 「この問題は誤差が大きくなりそう...」といった直感をはたらかせてほどよい許容誤差を設定しましょう。精進あるのみ？ 理想的には、IEEE 754 の倍精度浮動小数点数で想定解の入力/計算/出力を行ったときに発生する誤差を上から評価し、それを含むような許容誤差について考えるべきです。が、難しいのでここはとりあえずなあなあでもいいです(浮動小数点数は人類が扱うには難しすぎるので)。

個人的に、テストケースにおける想定解と真の値との誤差は問題文で設定されている許容誤差より 2-3 桁小さいことが多い印象があります。 誤差をランダムウォークだと思うと、プログラム中で N 回 \varepsilon の誤差が生まれる足し算を行うと誤差の絶対値の期待値は \varepsilon\sqrt N なのに対し、理論的に抑えられるのは N\varepsilon までなのでそんな感じかもしれません。 引き算などで桁落ちしたりすると計算結果の誤差はさらに大きくなりえますし、実装の方針でも誤差の出方は変わるのでゆるめに取ることを心がけるほうがいいかもしれません。

想定解編

想定解を書くまではとくに気をつけることはありません。好きに問題を作って想定解を書きましょう。 普通に誤差ジャッジ問を解くときに気をつけるべきことは妥当に気をつけておきましょう。

あと、問題設定をあまり変えずに誤差にやさしくする方法があればそのようにするほうがうれしいことがあります。 「最適解より最適値を求めさせる」とかは実行しやすい気がします。

writer作業編

writer が残りやっておく作業は

  • テストケースを作る
  • ジャッジを書く
  • 証明を書く

とかだと思います。

テストケースを作る

想定解では提出できる長さ/速さのコードを書くことになりますが、テストケースを作るときは多少時間がかかってもいいので誤差が出にくそうな方針を取ったり、途中まで有理数や a+b\sqrt c のような形の数を計算するライブラリを使って exact な値を保持したり、区間演算ライブラリなどを使って丁寧丁寧丁寧に真の値を評価するようにするとよいです。 想定解の誤差がちゃんと評価できている場合は想定解をそのまま利用してもいいです。 この段階で真の値の評価がかなり難しかったりする場合は、問題をそもそも成立させられない（現実的な計算資源で正しい値に近い値を出すことが難しい）可能性を考えておいたほうがいいかもしれません。

ジャッジを書く

testlib.h とかが有名で、誤差ジャッジも入っています。 誤差ジャッジに設定する許容誤差の値は問題文に書いたそれではなく、想定解から許容範囲を全部含むようにした許容誤差の値に設定しておきましょう。 ジャッジ側で気をつけることは、ジャッジが出力を受け取るところや、許容誤差の境界を計算するところにも誤差が入る可能性があるところです。testlib.h はこのあたりも吸収してくれたはず？です。 不安ならここでさらに許容誤差をドンと倍にしておくといいです。これで変なACが出るようになることはめったにないので基本困りません。

証明を書く

証明を書きましょう。誤差が一定以内に収まることを証明するのは難しいです。頑張りましょう。無理だったら強いtesterさんを呼びましょう。それでも無理だったら、とりあえず許容誤差をもうちょっとゆるくしておきましょう。場合によっては正当性がないかもしれないと思いながら問題を出すことになります。

tester作業編

ここまでの作業に嘘が混入していないか確かめましょう。

丁寧丁寧丁寧に真の値を評価して、許容誤差ギリギリを攻めてみるのも仕事のひとつです。 許容誤差の内側であることが証明できる値を入れて落ちたら、正しくないです。 外側であることが証明できる値を入れてACになってもジャッジに問題はありません。

許容誤差ギリギリを攻めて落ちる落ちないをしたところで防げる不幸せはあんまりないと思います（たとえば、「高橋君ボール1号」に sample 1 における f(t) が 100.00000099999999999999999999999 程度になる 100.000000241453007005241418874476を提出すると全ケースWAになりますが、ここの非厳密さで不幸せになったひと、ほとんどいなさそうです）が、問題文に嘘を書かないことがしたくないですか？したくない場合、にゃん。

道具編

知っておくと便利かもしれません。

  • testlib.h
    • writer/tester の強い味方。わりといろいろ対応してくれているので、ジャッジに使うと便利です。
  • boost/multiprecision/cpp_dec_float.hpp
    • boost の多倍長浮動小数点数型。AtCoder や yukicoder などのコンテストサイトでも使えてうれしい。有効桁数は好きに増やせますが、「真の値」について正しい評価を行うのは難しいので注意しましょう。see also : Rump の例題
  • boost/rational.hpp
    • boost の有理数型。boost::multiprecision::cpp_int と合わせて使うともっと強力に。AtCoder や yukicoder などのコンテストサイトでも使えてうれしい。exact な値を計算できるので、結果が有理数にならなくても途中まで有理数で計算したりするのが有効な場合もあります。
  • kv verifiedby.me
    • C++ で区間演算を行えるライブラリ。入出力も適切に処理してくれて、真の値を評価するのにとても便利。オンラインジャッジには入っていないがちなので、手元でテストケースを作ったり、無理矢理ヘッダファイルをコピペして提出することになりがち(?)

おしまい

浮動小数点数を扱うのは難しいので \mathbb{F}_p の問題を作るほうが楽なことがわかりました！ いかがでしたか？

数え上げ 𝓛𝓞𝓥𝓔...

  1. ところで、整数で出力する問題で、30 と出力すべきところに 30.0 とか 3e1 とか出力しても正しい値ではあります。このあたりは...うごごご 実数出力の問題はここに目を向けざるを得ないということなのかも？↩
  2. なんならこのネタでエイプリルフールコンあたりに1問提供しようかなと思っているくらい腑に落ちてない文なんですけど、慣習ってこわくないですか？↩