EDPC-J Sushi - blogskol

まず状態数に着目すると、寿司1個の皿、2個の皿、3個の皿の数だけ注目すればいいので $O(N ^3)$
期待値の問題は終了状態から再帰でdpをやるのが定石なのでする

$(a,b,c)$ : $1$ 個の皿、 $2$ 個の皿、 $3$ 個の皿がそれぞれ $a,b,c$ 枚の時の期待値

と置くと遷移は、zを0個の皿の数 $（=n-a-b-c）$ と置いて

$1.(a,b,c)⇨(a,b,c)$ 確率: $\frac{z}{n}$
$2.(a,b,c)⇨(a-1,b,c)$ 確率: $\frac{a}{n}$
$3.(a,b,c)⇨(a+1,b-1,c)$ 確率: $\frac{b}{n}$
$4.(a,b,c)⇨(a,b+1,c-1)$ 確率: $\frac{c}{n}$

なのでこれを無限ループにならないように無限和を扱いつつ書けばいい
以下 $(a-1,b,c)$ , $(a+1,b-1,c)$ , $(a,b+1,c-1)$ をそれぞれ $A,B,C$ と書くことにする

無限和の計算をいきなりすると頭が壊れるので丁寧に有限回の操作を計算する
$i$ 回で $(a,b,c)$ から脱出する時の期待値は

$i$ 回目で出る確率 $P=(\frac{z}{n})^{i-1}\frac{a+b+c}{n}$

$i$ 回目以降の期待値 $E=(1+A)\frac{a}{a+b+c}+(1+B)\frac{b}{a+b+c}+(1+C)\frac{c}{a+b+c}$

$P\times(i-1+E)=(\frac{z}{n}) ^{i-1}\frac{a+b+c}{n}(i+\frac{Aa+Bb+Cc}{a+b+c})=\frac{1}{n}(i(a+b+c)+Aa+Bb+Cc)$

これを $i$ が $1$ から $∞$ まで合算するから

$(a,b,c)=\sum_{i=1}^{∞}(\frac{z}{n}) ^{i-1}\frac{1}{n}(i(a+b+c)+Aa+Bb+Cc)$

$\sum_{i=1}^{∞}(\frac{z}{n}) ^{i-1}=\frac{n}{n-z}$

$\sum_{i=1}^{∞}(\frac{z}{n}) ^{i-1}i=\frac{n ^2}{(n-z) ^2}$

$∴(a,b,c)=\frac{1}{n-z}(Aa+Bb+Cc)+\frac{n}{(n-z) ^2}(a+b+c)$

あとは
・寿司のない皿から寿司を取らない
$・(0,0,0)=0$
などに注意して実装する

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

#define REP(i,n) for(int i=0;i<n;i++)
using ld=long double;

int v[4];
ld n,dp[301][301][301];
ld f(int a,int b,int c){
  if(dp[a][b][c]>=0)return dp[a][b][c];
  ld res=0,z=n-a-b-c;
  if(a)res+=a*f(a-1,b,c);
  if(b)res+=b*f(a+1,b-1,c);
  if(c)res+=c*f(a,b+1,c-1);
  res*=1/(n-z);
  res+=(a+b+c)*n/((n-z)*(n-z));
  return dp[a][b][c]=res;
}

int main(){
  cin>>n;
  REP(i,n-0.1){int x;cin>>x;v[x]++;}
  REP(i,301)REP(j,301)REP(k,301)dp[i][j][k]=-1;
  dp[0][0][0]=0;
  cout<<fixed<<setprecision(12)<<f(v[1],v[2],v[3])<<endl;
}

Submission #11363887 - Educational DP Contest