hogloidのブログ

へなちょこ

Codeforces #152 div1C,div2E Piglet's Birthday

URL http://www.codeforces.com/contest/249/problem/C

問題概要

棚がN個ある。
それぞれの棚には、最初、未開封のハチミツ瓶がa[i]個入っている。
q回イベントがある。
それぞれのイベントでは、棚uからランダムにk個ハチミツ瓶を選び、それらを開けて、棚vに入れる。
それぞれのイベント後、未開封のハチミツ瓶を一つも含んでいない棚の数の期待値 を小数で出力せよ。

N,q<=100000
0<=a[i]<=100
k<=5
u,v<=N










方針

確率dpです
dp[i][j]=棚番号iで 未開封のハチミツ瓶の数がj となる確率
とすると、未開封のハチミツ瓶の数は絶対に増えないのでうまく行きます。
最初に瓶がない棚もあることに注意

using namespace std;
static const int INF =500000000;

int n;
double dp[100005][105];
double tmp[105];
int init[100005],has[100005];
double C[1000005][10];
//コンビネーション
int main(){
	for(int i=0;i<105;++i) for(int j=0;j<105;++j) dp[i][j]=0;
	for(int i=0;i<1000005;++i){
		C[i][0]=1;
		for(int j=0;j<min(i,9);++j) C[i][j+1]=C[i-1][j]+C[i-1][j+1];
	}
//コンビネーションを予め計算
	scanf("%d",&n);
	double cur=0;
	for(int i=0;i<n;++i){
		scanf("%d",&init[i]);
		has[i]=init[i];
		dp[i][init[i]]=1;
		if(init[i]==0) ++cur;
	}
	int q;scanf("%d",&q);
	while(q--){
		int u,v,k;scanf("%d%d%d",&u,&v,&k);--u;--v;

		cur-=dp[u][0];
		for(int j=0;j<105;++j) tmp[j]=0;
		for(int i=0;i<=init[u];++i) if(dp[u][i]>1e-30){
			for(int j=0;j<=k && j<=i;++j){
//j:=いくつ未開封の瓶を選ぶか
				tmp[i-j]+=dp[u][i]*C[i][j]*C[has[u]-i][k-j]/C[has[u]][k];
//has[u]個からk個選ぶとき、i個の未開封瓶がj個選ばれる確率
			}
		}
		for(int j=0;j<105;++j) dp[u][j]=tmp[j];
		has[u]-=k;
		has[v]+=k;
		cur+=dp[u][0];
		printf("%.10f\n",cur);
	}


	return 0;
}

cinはただでさえ遅いですが小数に対してはめちゃくちゃ遅かった。注意