abc184_D - increment of coins

Solution Overview

This problem can be solved by Probability Dynamic Programming. We can calculate the expected times of the operation from that of when one more coin is there.

if we define dp[i][j][k] as the expected times of the operation from the situation we have (i,j,k) coins, we can find this value by:

dp[i][j][k]=(i/i+j+k)(1+dp[i+1][j][k])+(j/i+j+k)(1+dp[i+1][j+1][k])+(k/i+j+k)(1+dp[i][j][k+1])

Code

int A,B,C;
double dp[105][105][105];

double dfs(int i,int j, int k){
    if(dp[i][j][k]) return dp[i][j][k];
    if(i==100 || j==100 || k==100)return 0.0;
    double ret=0.0;
    ret+=((double)i/(double)(i+j+k))*(1.0+dfs(i+1,j,k));
    ret+=((double)j/(double)(i+j+k))*(1.0+dfs(i,j+1,k));
    ret+=((double)k/(double)(i+j+k))*(1.0+dfs(i,j,k+1));
    dp[i][j][k]=ret;
    return ret;
}
signed main(){
    scanf("%lld %lld %lld",&A,&B,&C);
    printf("%.9lf\n",dfs(A,B,C));
}

テーブル

int A,B,C;
double dp[105][105][105];

signed main(){
    scanf("%lld %lld %lld",&A,&B,&C);
    for(int i=99;i>=0;i--){
        for(int j=99;j>=0;j--){
            for(int k=99;k>=0;k--){
                dp[i][j][k]=0.0;
                if(i<100)dp[i][j][k]+=((double)i/(double)(i+j+k))*(1.0+dp[i+1][j][k]);
                if(j<100)dp[i][j][k]+=((double)j/(double)(i+j+k))*(1.0+dp[i][j+1][k]);
                if(k<100)dp[i][j][k]+=((double)k/(double)(i+j+k))*(1.0+dp[i][j][k+1]);
            }
        }
    }
    printf("%.9lf\n",dp[A][B][C]);
}