DPまとめコンテスト J - Sushi

J - Sushi

概要

数列がある（各皿に乗っている寿司の個数）。「からを等確率で選び（サイコロを振る）、選んだ数字をとするときならから1を引く」という操作（寿司を食べる）を繰り返す。このとき、がすべて0になるまでの操作回数の期待値を求めよ。

制約

方針

：寿司個の皿が枚あるとき、すべての寿司がなくなるまでの操作回数の期待値
とする。計算手順が複雑なのでメモ化再帰で解く。

感想

DP更新のところが証明できていない。。
（期待値を漸化式で推移させている？）

解答

Submission #3964795 - Educational DP Contest / DP まとめコンテスト

#include <bits/stdc++.h>
 
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define rep(i,n) FOR(i,0,n)
#define RFOR(i,a,b) for(int i=(a)-1;i>=(b);i--)
#define rrep(i,n) RFOR(i,n,0)
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
 
int n;
const int max_n = 303;
double dp[max_n][max_n][max_n];
// dp[i1][i2][i3]
// :寿司j個の皿がij枚あるとき、すべての寿司がなくなるまでの操作回数の期待値
 
double calc(int i, int j, int k){
	if(!i && !j && !k) return 0.0;
	if(dp[i][j][k] > 0) return dp[i][j][k];
 
	int l = i + j + k;
	double ret = 1.0 * n / l;
	if(i) ret += 1.0 * i / l * calc(i-1, j, k);
	if(j) ret += 1.0 * j / l * calc(i+1, j-1, k);
	if(k) ret += 1.0 * k / l * calc(i, j+1, k-1);
 
	dp[i][j][k] = ret;
	return ret;
}
 
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
 
	cin >> n;
 
	int cnt[4] = {};
	rep(i, n){
		int a;
		cin >> a;
		cnt[a]++;
	}
 
	rep(i, max_n) rep(j, max_n) rep(k, max_n) dp[i][j][k] = 0;
 
	cout << fixed << setprecision(11) << calc(cnt[1], cnt[2], cnt[3]) << endl;
}