技術室奥プログラミングコンテスト #3 E - デフレゲーム

期待値の問題を解きたかったので

問題のリンク

E - デフレゲーム

考察

とりあえず小さいn で実験。
・n = 2
サンプル1 通り、0.25 * 1 + 0.25 * 2 + 0.5 * 3 = 2.25。
ここで、3を1+2 と見て、(0.25 + 0.5) * 1 + (0.25 + 0.5) * 2 = 2.25 と見る。これは、 (i の目が出てi 円貰える確率) * i に書き換えたということである。
ここで、全ての目が出る確率は等しいので(i の目が出てi 円貰える確率) はi に依らない値になる。つまり、求めるものは (i の目が出てi 円貰える確率) * となる。

・i の目が出て、i 円貰える確率
これを言い換えると、i の目が出てかつ、これまで出た目のいずれも2 回以上出現していないという確率である。K回目にi が出てくるとすると、K-1 回目までに出る目がi 以外かつ、重複していない確率は、

となる。K回目にi が出てくる確率は 1/n でこれをかける。
あとは、1 <= K <= n でこれを足せばいい。

結局、求めるものは、

以下実装

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdio>
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<=n;++i)
using namespace std;
template<class T>bool chmax(T &a, const T &b) { if(a < b){ a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if(a > b){ a = b; return 1; } return 0; }
int main()
{
  double n; cin >> n;
  double res = 1;
  double x = 1;
  rep1(i,(int)n) {
    x *= (n - i) / n;
    res += x;
  }

  res /= n;
  res *= (n + 1) * n / 2;
  printf("%.9f\n", res);
  
  return 0;
}