ABC154D-Dice in Line
問題概要
個のサイコロから連続する個選んだときの出る目の合計の期待値の最大値を求めよ。
制約
考察
連続する個の期待値の最大値を求めれば良いので、累積和を応用してあげると良い。
それぞれの期待値は、
と求められることを使うと良い。
d.cpp
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <iomanip>
using namespace std;
int main() {
int N, K; cin >> N >> K;
vector<double> a(N);
vector<double> S(N+1, 0.);
for(int i = 0; i < N; i++) {
double b; cin >> b;
a[i] = (b+1) / 2;
S[i+1] = S[i] + a[i];
}
double ans = 0.;
for(int i = 0; i < N-K+1; i++) {
ans = max(ans, S[i+K] - S[i]);
}
cout << setprecision(10);
cout << ans << endl;
return 0;
}