【abc154-D】 小数の表示桁数/累積和

※注意
この記事は、もともと自分用に執筆したが気が向いて公開してしまったものです。ので、各所にお気持ちが伝わりづらい(伝わらない)言い回しやコードが散見されるかもしれませんがご了承ください。

まえがき

AtCoder Beginner Contest 154(あとから)。
A~Cは簡単に通せた。Dも簡単だったけど恥ずかしながら二悶着くらいあったのでメモレベルで残しておく。
※abc154-D(Dice in Line).Difficulty: 405

本編

全然関係ないテーマ2つを吸収しました。

小数の表示桁数

本日の戦犯。「なお、想定解答との絶対誤差または相対誤差が　$10^{-6}$ 以下であれば正解として扱われる。」に抵触したようです。
ただまあ原因がわかってしまえばそれだけなので要点だけまとめる。
ずっと一番上の方法で出力させててWA吐きまくったんだけどこの3つの違いについて。

free.cpp

    cout<<ans<<endl;

    cout<<setprecision(8)<<ans<<endl;
    
    cout<<fixed<<setprecision(8)<<ans<<endl;

• cout をdouble型に対して適用すると、デフォルトでは整数部、小数部合わせて6桁が出力される。
• setprecision(n) をつけると、整数部、小数部合わせてn桁が出力される。
• fixed をつけると、小数点以下だけ見てn桁が出力される(普通に整数部分も出てくるよ)。

それだけ。「この問題ansは絶対整数もしくは~~~.5だから誤差とか生まれないだろ」とか思ってたら出力の問題でした。反省。確かに最大で500*200000~10000000くらい行くから6桁じゃ足りないね。

まあ競プロしてる上ではいつも cout<<fixed<<setprecision(10)<<ans<<endl; とかにしとけば全く問題はなさそうだけど、一応知識としては持っておこう。

累積和

この問題でD問題ぽい要素があるとすればたぶんこのアルゴリズム。舐めたこと言ってるけど最初普通にこれ使わずにTLE吐いてるから軽くメモって意識に入れとく。

abc154/d.cpp

    double expect[n-k+1];
    double sum;
    for(int i=0; i<n-k+1; i++) {
        sum = 0;
        for(int j=i; j<i+k; j++) {
            sum += dice[j];
        }
        expect[i] = sum;
    }

    double ans = *max_element(expect, expect+n-k+1);

はじめに安直に書いたコードの一部。要は毎回K個隣接するダイスの期待値の総和を計算してたんだけど、これだと計算量はざっくり $O(NK)$ くらい。確かにこれは入力によっては全然間に合わない。

この解決には累積和の考え方を使うといいぽいんだけど、これ本当に大したことなかった。
そこまでの総和を計算した配列を用意しておけば、その後は一瞬である区間の総和を求められる(考えればわかる)。前処理が $O(N)$ 。それ以降はもうO(1)。

本問では配列を作るまでもないなてなったので下のようにコードを書きました。細かいことは置いといてね。

abc154/d2.cpp

    double ans = sum;
    for(int i=1; i<n-k+1; i++) {
        sum = sum + dice[i+k-1] - dice[i-1];
        if(sum>ans) ans = sum;
    }

abc154-D のACコード

abc154/d2.cpp

# include <bits/stdc++.h>
using namespace std;

int main() {
    int n,k;
    cin>>n>>k;
    double dice[n];
    for(int i=0; i<n; i++) cin>>dice[i];

    for(int i=0; i<n; i++) {
        dice[i] = (dice[i]+1)/2;
    }

    double sum = 0;
    for(int i=0; i<k; i++) {
        sum += dice[i];
    }

    if(n==k) {
        cout<<sum<<endl;
        return 0;
    }

    double ans = sum;
    for(int i=1; i<n-k+1; i++) {
        sum = sum + dice[i+k-1] - dice[i-1];
        if(sum>ans) ans = sum;
    }

    cout<<fixed<<setprecision(8)<<ans<<endl;

    return 0;
}

おしまい

梅酒飲んでプログラム書くと思ったより色々ミスるね