atcoder ABC 154D問題が解けません。

Question

atcoder ABC 154D問題が解けません。

https://atcoder.jp/contests/abc154/tasks/abc154_d

なぜ間違えた答えになるのかわからないので、教えてくれるとうれしいです。

#include<iostream>
#include<algorithm>
#include<vector>
#define rep(i, n) for (int i=0; i<(n); i++)
using namespace std;

int main(){
    int K, N; cin >> N >> K;
    double p[N], tot=0, ans;
    rep(i, N) cin >> p[i];
    rep(i, K){
        tot += (p[i]+1)/2;
    }
    ans = tot;;
    for(int i=1; i<N-K+1; i++){
        tot += (p[i+K-1]+1)/2 - (p[i-1]+1)/2;
        if(ans < tot) ans = tot;
    }
    //rep(i, N-K+1) cout << sum[i] << " ";
    //cout << endl;
    cout << ans << endl;
}

Comments

[SHOMI]

端から順にひとつずつ加減算しているので誤差蓄積しているのでは？
…と思いましたが期待値は0.5刻みなので誤差は出なさそうですね

Answer 1

実は解けています。

ではなぜWAになっているのかと言うと、出力する桁数が足りないからです。

cout << ans << endl;

では、6桁ぐらいしか出力してくれず、精度不足でWAになります。

以下のように、printfや、setprecisionを使えば、アルゴリズム部分を一切変更せずとも AC できます。

printf("%.10f\n", ans);

https://atcoder.jp/contests/abc154/submissions/11016435

Comments

[goro_gnm]

出力の精度は考えたことがありませんでした！
具体的に教えてくださりありがとうございます、勉強になりました！

Answer 2

cout << ans << endl;

ここで指数表記で出力されてしまうからでは？

例：
N:200000
K:200000
piをすべて1000
とした場合に
1.001e+08
と出力されてしまい、

なお、想定解答との絶対誤差または相対誤差が 10^−6以下であれば正解として扱われる。

に引っかかっているのでしょう。

Answer 3

なぜ間違えた答えになるのかわからないので、

間違えた答えとは具体的になんですか？

double の計算ですが、2で割って、0.5 を含む値になり、これらの和なら
2進計算で誤差は出ません。

double p[N] という可変長配列は GNU の C++ (g++) では拡張機能として
コンパイルエラーになりませんが、その拡張機能は使えないオプションで
判定しているのではありませんか?

vector<double> p(N); にしたらどうなりますか？

Comments

[goro_gnm]

間違えた答えとは、atcoderで提出したときにwrong answerになるという意味で言っていました。明確でなく、すみません。

原因は出力する際の精度が足りなかったことだったようです、回答ありがとうございました！