atcoderでWAが２つだけ出てしまいます。

atcoderの次の問題を解いているのですが、自分の回答だと2つのケースでWAが出てしまいます。
自分で考えても理由が分からないので、教えてくれるとうれしいです。

問題URL
https://atcoder.jp/contests/abc148/tasks/abc148_e

問題文
0 以上の整数 n に対し、 f(n) を次のように定義します。
f(n)=1 (n<2 のとき)
f(n)=nf(n−2) (n≥2 のとき)
整数 N が与えられます。f(N) を 10 進法で表記した時に末尾に何個の 0 が続くかを求めてください。

制約
0≤N≤10^18

↓自分が書いたコード

c++
1#include<math.h>
2#include<iostream>
3typedef long long ll;
4using namespace std;
5
6int main(){
7    ll N, plus, ans=0;
8    cin >> N;
9    if(N%2 != 0){
10        cout << 0 << endl;
11    }else{
12        for(int i=1; i<=(log(N/2)/log(5)); i++){
13            plus = N/(2*pow(5,i));
14            ans += plus;
15        }
16        cout << ans << endl;
17    } 
18}

行動規範の内容に同意します

回答1件

ベストアンサー

~~今スマホなので自信はないですが、見たところ論理的には合っていそうなので可能性としては浮動小数点誤差ではないでしょうか。~~

C
1for(int i=1; i<=(log(N/2)/log(5)); i++){

ここがかなり怪しく、境界値条件で引っかかっている物と思われます。
例えばN=50のとき、正しくはi<=2になって欲しいですが、logを挟んでいるため誤差が乗り限りなく2に近いが2に満たない価になっている可能性があります。

家に着いたので色々確認をとってみました。

[1]log計算による浮動小数点誤差
やはりcoutのprecisionを弄らないとcoutで出ない程度の誤差がlog(125)/log(5)などで見られます。
ただ、適当に値を試した範囲ではたまたま誤差が+側に触れており、やはりWAの原因ではなさそうです
(環境依存な可能性もあり、いずれにせよこの条件はやめた方が良いと思いますが)

[2]powの計算結果
これも同じ理由で誤差が出ました。
例えば pow(5,24) を試すと 59604644775390624 となり5の倍数ではないことから明らかに誤差を持っています。

整数の問題ではできるだけ怪しい浮動小数点演算は使わず整数で計算した方が良さそうですね。

投稿2019/12/27 08:49

編集2019/12/27 11:49

退会済みユーザー

総合スコア0

退会済みユーザー

2019/12/27 08:52

5のi乗をキープしてN/2との比較を終了条件にした方がが安全ですね。

yumetodo

2019/12/27 08:54

いや、そこは大丈夫かなと思います(手元で実験した感じ

退会済みユーザー

2019/12/27 09:08 編集

感じで判断せず理屈で判断しましょう。計算打ち切りによる浮動小数点誤差は必ず乗るのでN=2*5^kを入れたときにlog(N/2)/log(5)の計算結果として整数は返ってきません(k=1除く) 除算結果の浮動小数点誤差が必ず+になる保証がない限りはループの終了条件に影響します。「かなり怪しい」と言ったのはこの部分が原因でWA?が出ている可能性が強いという意味で、仮に他に原因があったとしてもここ自体はバグの原因になります。 ※誤字修正＋誤解を招きそうな所に追記

goro_gnm

2019/12/27 10:02

なるほど、たしかにそれはWAの原因になりえますね。不動小数点誤差について考慮したことなかったので、心にとめるべきものとしてメモしておきます。ありがとうございます。しかし、ループを多めに回してもWAはなくなりませんでした。（『5のi乗をキープしてN/2との比較を終了条件にする』はどういうことでしょう？とりあえず安易に for(int i=1; i<=(log(N/2)/log(5))+1; i++) として提出してみました。）これでだめということは他に原因があるということですかね。

退会済みユーザー

2019/12/27 10:25

要は5を何乗すればN/2になるかという値をループの条件にするなら5のi乗とN/2との比較をループの条件にした方が安全という感じです。 5のi乗はループの中で計算してますし。

退会済みユーザー

2019/12/27 10:29

あ、powこれdouble型帰ってきてません？

yumetodo

2019/12/27 11:05

それですね。

goro_gnm

2019/12/27 11:46

double型で帰ってくると何がだめなのでしょうか...？

退会済みユーザー

2019/12/27 11:58

回答を更新したので、そちらを見てもらったら良いかと思いますが、浮動小数点は誤差を含む場合がほとんどなので数式上正しい記述をしたとしても処理上正しい値が入っているとは限りません。 powは一見整数の累乗をしているから良さそうに見えますが、値がdoulbe型で表現されているということは、整数であっても誤差を含む可能性があるわけです（詳細は倍精度浮動小数点数の表現形式を理解しないと難しいのですが）

goro_gnm

2019/12/28 14:39

なるほど、理解が怪しいので不動小数点誤差について復習しようと思います。この場合これを正そうと思ったら、pow()関数を使わずに自分でforループ回して累乗を計算するというのが適当なのでしょうか？そのように書き直して提出したらOKになりました！ありがとうございます！

退会済みユーザー

2019/12/28 14:56

今回はpowとlogを使わない方が良いですね。 logはたまたま全部誤差が+に振れたので大丈夫だったみたいですけど。正確ではないですが、すごーく平たい説明をすれば例えば0以上9以下の整数の個数は10個ですが、同じ範囲の実数の個数は無限なのでこの範囲の全ての実数を正確に表現するには無限bit必要になってしまいます。そこで、誤差はあるけどN桁までなら保証するよ、って表現方法が浮動小数点です。今回powでは整数の計算しかしてませんが、整数であっても「N桁までなら保証するよ」というあり方は変わらないのでどでかい整数で誤差が出た訳です。厳密に言えばその桁数も10進数の桁数ではなかったり、単一の浮動小数点数では問題にならない程度の誤差が、浮動小数点数同士の演算を繰り返すことにより問題になったりするケースがあったりするので、詳しいことは調べてみてください。

yumetodo

2019/12/28 15:03

というか今回のに限っては、文字列に変換してしまったほうが速かったんじゃないかなと。strtolとかC++17のstd::to_charsとかで

退会済みユーザー

2019/12/28 15:08

それはf(n)を計算して文字列にして0の個数を調べるということですか？

yumetodo

2019/12/28 16:41

です。そんなに遅くならないと思うんですがね・・・。

退会済みユーザー

2019/12/28 16:47

計算すべきはNが偶数の時のみですが、f(2M)=2^M*M!になり、0≤M≤5*10^17なので現実的に無理かと。