Dice in Line [AtCoder Beginner Contest 154 D]

https://atcoder.jp/contests/abc154/tasks/abc154_d

前提知識

• 期待値の線形性

解説

https://atcoder.jp/contests/abc154/submissions/10001499

期待値の線形性というのがある。
それぞれのサイコロは独立に期待値を考えることができるので、合計の期待値は期待値の合計と等しくなる。
つまり、「隣接するK個のサイコロを選んで独立に振った時に出る目の合計の期待値」は
「隣接するK個のサイコロを選んで独立に振った時に出る目の期待値の合計」と等しい。
なので、最大化したい値の計算が区間和に帰着した。
隣接するK個のサイコロの選び方はN-K+1通りあるので、区間和が高速に求まれば、問題が解けたことになる。

これは累積和を使っても解けるが、自分の解法ではスライドしながら差分計算する方法でやっている。
ある隣接するK個の区間を計算し終わったら、その区間を右に1つ動かすことで、
先頭を引いて、追加されたサイコロ分を追加することで差分を計算する。
これで高速に区間和を求めることができ、計算しつつmaxを取ると答え。

int N, K, p[201010];
double e[201010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> K;
    rep(i, 0, N) cin >> p[i];

    rep(i, 0, N) e[i] = 1.0 * (1 + p[i]) / 2;

    double tot = 0;
    rep(i, 0, K) tot += e[i];

    double ans = tot;
    rep(i, K, N) {
        tot = tot + e[i] - e[i - K];
        chmax(ans, tot);
    }
    printf("%.10f\n", ans);
}