SRM504.5 Div2 Hard(1000) TheTicketsDivTwo

TheTicketsDivTwo

動的計画法。列の人数とm番目の友人の位置ごとに確率を覚えておく。

class TheTicketsDivTwo{public:
double find( int n, int m, int k )
{
    //  [ダイスを投げた回数][列の人数][m番目の人の位置]
    double T[11][11][11] = {{{0}}};
    T[0][n][m] = 1;

    double ans = 0;
    
    for ( int i=0; i<k; i++ )
    for ( int j=1; j<=n; j++ )
    for ( int l=1; l<=j; l++ )
    {
        if ( j == 1 )
        {
            ans += T[i][j][l];
            continue;
        }

        //  4
        if ( l == 1 )
            ans += T[i][j][l] * 1./6;
        //  奇数
        T[i+1][j][l==1?j:l-1] += T[i][j][l] * 3./6;
        //  偶数
        if ( l != 1 )
            T[i+1][j-1][l-1] += T[i][j][l] * 2./6;
    }

    for ( int i=1; i<=n; i++ )
        ans += T[k][i][1];
    
    return ans;
}};