[AtCoder] ABC 154 D – Dice in Line

2020年2月9日2020年12月15日

問題

方針

サイコロの出る目が \( a \) まであるとき、このサイコロの出る目の期待値は、

\[ \dfrac{a(a + 1)}{2} \times \dfrac{1}{a} = \dfrac{a + 1}{2}\]

となります。したがって、累積和などを用いて最大となる値を全探索します。

コード

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


int main() {
    int N, K;
    cin >> N >> K;
    ll p[N];
    ll a[N + 1]{};
    for (int i = 0; i < N; i++) {
        cin >> p[i];
        a[i + 1] = a[i] + p[i];
    }
    double ans = 0;
    ll sum = 0;
    ll t = 0;
    for (int i = K; i <= N; i++) {
        t = a[i] - a[i - K] + K;
        sum = max(sum, t);
    }
    ans = (double)sum / 2.0;
    printf("%.6f\n", ans);
    
    return 0;
}