これはなに
お気持ち表明ではないです。
「真の値との誤差が○○なら AC」←非ワクワク ←ホンマか? こう書いてもACの十分条件なのでワンチャン 0.0 を AC にしてもよいのでそこそこワクワク感あるのでは?
— 物理好き (@butsurizuki) 2023年3月25日
これをみたので。
比較的ねむいのでこのツイートに関する話ではないかもしれません。
以下では「iff で判定可能」というのを、ある数 $x$ が与えられたときにある数 $\alpha$ からの相対誤差もしくは絶対誤差が $\varepsilon$ 以下であるか否かを誤差なしで判定できることとします。
たぷ
解の真の値が 0 である場合、0.0 を AC としないとワクワクになります。1
まじめな話
浮動小数点数を出力しようとすると、符号?十進数列(.十進数列)?(e符号?十進数列)? みたいな形になることが多いと思います（ランダムにビット列を取ってくると nan のことも多いですか？そうかも）。 この形式の値は有限小数なので有理数として表すことができますね。
有理数として値が得られれば、ある代数的数 $\alpha$ からの絶対誤差もしくは相対誤差がある代数的数 $\varepsilon$ 以下であるかを厳密に判定することができますね（$\alpha$ を根にもつ多項式はあるとうれしいですね そもそも一般には $\alpha$ を持っておくために必要な気がしますけど）。
たとえばこれとかは iff で判定可能な問題です。
でも現実的に iff で判定可能な問題は少なくて、
この問題は解の真の値は代数的数になりますが、最小多項式の次数が $2 ^ {\Theta(N)}$ くらいになりそうな気がします。 証明していないのでふんわりしておきます。
解が代数的数にならない問題は iff で判定可能と言いにくいような気がします。
問題を準備する際に十分時間をかけ、許容範囲の上限と下限の十進展開をOLEぎりぎりまで評価してしまうくらいしか有効な手立てがないような気がします。
この手段を取ったとしても、適切な問題とテストケースを用意するとどれだけの精度で計算を始めればいいのかわからないような例が作れるような気がします（OLEぎりぎりの直下が $000000\ldots$ なのか $999999\ldots$ なのか（どちらも長い有限桁ののち $0$ や $9$ でない桁が出現するものとします）の判定が現実的には終わらないような場合があるかもしれません）。
そうでなくても、$10 ^ 8$ 桁以上正しいことを保証しながら計算を行うのは非常に骨が折れそうですね。
1ケースに1時間くらいかかると50ケースでは2日以上かかるので、計画的に準備をすることでなんとかなる場合があるかもしれません。
https://t.co/oa3wPYbDqR
— えびちゃん🍑🍝🦃 (@rsk0315_h4x) 2019年11月20日
2^27 くらいで OLE
$10 ^ 8$ 桁までは OLE にならなさそうな話。
そもそも $10 ^ 8$ 文字の文字列どうしを浮動小数点数として大小比較するのも多少時間がかかりそうな気がしますね。
本題
1e100 とか -3.14e-3 みたいな値から有理数を得る関数を書いてみました。
構文解析には自信がないロボットなので、みなさまの助力をおまちしています（？）。
$\dfrac ab\times10 ^ c\ (10\nmid a,b)$ みたいな形式で表すのもいいかなと思ったんですけど、boost::rational の恩恵にあずかりたかったので。
using big_integer = boost::multiprecision::cpp_int;
using big_rational = boost::rational<big_integer>;
const auto decimal_floating_point_number_literal_to_rational{[](const string& s) -> optional<big_rational> {
vector<pair<unsigned long, unsigned long>> sub_idx(5, {size(s), size(s)});
unsigned long state{}, index{};
bool positive{true}, dup_sign{false};
const auto change_state{[&sub_idx, &state, &index, &dup_sign](unsigned long next_state){
dup_sign = false;
for(; state < next_state; ++state){
sub_idx[state].second = index;
sub_idx[state + 1].first = index;
}
}};
sub_idx[0].first = 0;
for(const auto c : s){
if(state == 0){
if(!dup_sign && (c == '-' || c == '+')){
if(c == '-')positive = false;
dup_sign = true;
}else if('0' <= c && c <= '9')change_state(1);
else if(c == '.')change_state(2);
else return {};
}else if(state == 1){
if('0' <= c && c <= '9');
else if(c == '.')change_state(2);
else if(c == 'e' || c == 'E')change_state(3);
else return {};
}else if(state == 2){
if('0' <= c && c <= '9');
else if(c == 'e' || c == 'E')change_state(3);
else return {};
}else if(state == 3){
if(!dup_sign && (c == '-' || c == '+'))dup_sign = true;
else if('0' <= c && c <= '9')change_state(4);
else return {};
}else if(state == 4){
if('0' <= c && c <= '9');
else return {};
}
++index;
}
if(sub_idx[2].first != sub_idx[2].second)++sub_idx[2].first;
if(sub_idx[3].first != sub_idx[3].second){
++sub_idx[3].first;
if(s[sub_idx[3].first] == '+')++sub_idx[3].first;
}
sub_idx[3].second = sub_idx[4].second;
sub_idx.pop_back();
big_integer exponent{sub_idx[2].second - sub_idx[2].first};
exponent *= -1;
while(sub_idx[1].first != sub_idx[1].second && s[sub_idx[1].first] == '0')++sub_idx[1].first;
if(sub_idx[1].first == sub_idx[1].second)while(sub_idx[2].first != sub_idx[2].second && s[sub_idx[2].first] == '0')++sub_idx[2].first;
while(sub_idx[2].first != sub_idx[2].second && s[sub_idx[2].second - 1] == '0'){
--sub_idx[2].second;
++exponent;
}
if(sub_idx[2].first == sub_idx[2].second)while(sub_idx[1].first != sub_idx[1].second && s[sub_idx[1].second - 1] == '0'){
--sub_idx[1].second;
++exponent;
}
big_integer numerator{1}, denominator{1};
if(!positive)numerator *= -1;
numerator *= big_integer{s.substr(sub_idx[1].first, sub_idx[1].second - sub_idx[1].first) + s.substr(sub_idx[2].first, sub_idx[2].second - sub_idx[2].first)};
const auto pow_ten{[](big_integer n) -> big_integer {
big_integer r{1}, a{10};
while(n){
if(n & 1)r *= a;
a *= a;
n /= 2;
}
return r;
}};
if(sub_idx[3].first != sub_idx[3].second)exponent += big_integer{string_view{s}.substr(sub_idx[3].first, sub_idx[3].second - sub_idx[3].first)};
if(exponent < 0)denominator *= pow_ten(-exponent);
else numerator *= pow_ten(exponent);
return big_rational{numerator, denominator};
}};
これを使ってジャッジするの、遅くなるだけでうれしくなる人はそんなに多くないと思ってますけど、お好みでお使いください（？） バグってたらごめんなさいです
ところで
この主張自体はかなり同意なんだけど、それだと非ワクワクにするの難すぎ問題が…
— hotman (@hotmanww) 2023年3月26日
絶対にACが出る区間とACとWAどちらが出てもOKな区間と絶対にWAな区間を明示的に指定して二倍の区間をAC判定にする例のやつをすると良さそうかな https://t.co/JufwKvWGTm
こう書いてもいいと思いますけど、この条件を満たすかの判定が煩雑になるわりに問題やジャッジの振る舞い/コンテスタントが得る情報としてはあんまり増えないような気もします… どうでしょう？ こう書くのがダメではないので、こう書いてもいいと思います（想定解からの誤差よりよっぽどよいです なぜならば想定解からの誤差は悪いので）
おわりに
競プロと音ゲーを合成した競技を発明すればかなり大怪獣バトルができる可能性がある
— 物理好き (@butsurizuki) 2023年3月25日
洗濯機型音楽ゲームでぽかいこと勝負！
負けました（なんですか？）
🍑🍝🦃（ぽかパスタターキー（982766353型文字列））
- ほんとうに？数え上げで答えが 0 のときに 0.0 を AC にしなくても文句は出ないと思います↩
