期待値の線形性!!!
問題概要
個のサイコロが左から右に一列に並べてある。 番目のサイコロは目が となっていて、これらが当確率に出る。
隣接する 個のサイコロを選んでそれぞれ独立に振ったとき、出る目の合計の期待値の最大値を求めよ。
制約
考えたこと
出た!!!!!!!!期待値!!!!!!!!!!!
まず隣接する 個のサイコロを選ぶ方法を最適化せよと言われているけど、とりあえずまずは以下の問題を解いてみよう。元の問題を解くためには、まずはその部分的な問題を解いていくのがいいと思う。
個のサイコロがあって、それぞれ目の種類は だけある。
個のサイコロを振って出た目の和の期待値を求めよ。
まずサイコロ 1 個 (目の種類が ) だった場合は、
- の目が出る確率は
- の目が出る確率は
- ...
- の目が出る確率は
となるので、期待値は
=
となる。なおもっと簡単に、 の平均は であることは直感的にも納得できる。つまり最小が 1 で、最大が p で、その中点である が平均というわけだ。
期待値の線形性
それでは 個のサイコロの目の合計値の期待値はどうだろうか。実はこれはこんな風に簡単に考えることができる。
- 1 個目のサイコロの出す目の平均値は
- 2 個目のサイコロの出す目の平均値は
- ...
- 個目のサイコロの出す目の平均値は
よって、これらを合計して、 個のサイコロの目の合計値の期待値は
となる。
元の問題へ
こうして 個のサイコロから 個を選んだときの期待値を求めることには成功した。最後の問題は、この値が最大となるように 個を選びとることだ。
これは 個の値
の中から連続する 個の総和の最大値を求めればよい。ここまできたら累積和で求めることができる。累積和についてはここに。
なお、実装上の工夫として、 個の値
を一様に 2 倍して
という風にしても、最大となる 個の値は変わらない。最後に /2 をすればよい。こうすれば、最後の最後に /2 するまでは整数型のみで計算することができる。
#include <bits/stdc++.h> using namespace std; int main() { int N, K; cin >> N >> K; vector<long long> p(N); for (int i = 0; i < N; ++i) cin >> p[i], ++p[i]; // 1 足しておく // 累積和 vector<long long> s(N+1, 0); for (int i = 0; i < N; ++i) s[i+1] = s[i] + p[i]; // K 差を見ていく long long res = 0; for (int i = 0; i+K <= N; ++i) res = max(res, s[i+K] - s[i]); cout << fixed << setprecision(10) << (double)(res)/2 << endl; }