M-SOLUTIONS社のプロコンに参加しました.
C問題で累積積を書いて提出したのですが桁が大きすぎてWA. 解説をみたところ対数変換で累積和に直せば同じようなロジックで解けるとのことで実装して提出しました.
考え方
logで対数変換し,累積和を取りi
からi-k
の値を引くことでそれぞれの学期評価が求まります.
あとはそれを比較し答えを求めます.
c++にはlog10
という便利な関数があり,簡単に対数変換できることがわかりました.
また対数変換の際には誤差に対応する必要があるため少数型にします.
解いたコード
#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]
を比較するだけで良いのですが,気付きませんでした...
算数強くなりたい.