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はただでさえ遅いですが小数に対してはめちゃくちゃ遅かった。注意