M-SOLUTIONS プロコンオープン 2020 C 累積和で解く

M-SOLUTIONS社のプロコンに参加しました．

C問題で累積積を書いて提出したのですが桁が大きすぎてWA． 解説をみたところ対数変換で累積和に直せば同じようなロジックで解けるとのことで実装して提出しました．

atcoder.jp

考え方

logで対数変換し，累積和を取りiからi-kの値を引くことでそれぞれの学期評価が求まります． あとはそれを比較し答えを求めます．

c++にはlog10という便利な関数があり，簡単に対数変換できることがわかりました． また対数変換の際には誤差に対応する必要があるため少数型にします．

4学期の評価を求める場合(i=4, k=3)

解いたコード

#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <utility>
#include <vector>
#define rep(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)
#define reps(i, n) for (int i = 1, i##_len = (n); i <= i##_len; ++i)
#define rrep(i, n) for (int i = ((int)(n)-1); i >= 0; --i)
#define rreps(i, n) for (int i = ((int)(n)); i > 0; --i)
#define INF 1000000000000
#define MOD 1000000007

 
int main() {
    ll n, k;
    cin >> n >> k;
    vector<long double> a(n + 1, 0);
    vector<long double> csum(n + 1, 0);
    reps(i, n) cin >> a[i];
    reps(i, n) csum[i] = log10(a[i]) + csum[i - 1];
 
    long double pre = csum[k];
    for (int i = k + 1; i <= n; i++) {
        long double result = csum[i] - csum[i - k];
        if (pre < result)
            cout << "Yes" << endl;
        else
            cout << "No" << endl;
        pre = result;
    }
    return 0;
}

ほんとはA[i] < A[i-k]を比較するだけで良いのですが，気付きませんでした．．． 算数強くなりたい．