Hatena::Grouptopcoder

chokudaiの日記

 | 

2010-11-09

SRM 466 Div1 Medium LotteryPyaterochka

21:19 | SRM 466 Div1 Medium LotteryPyaterochka - chokudaiの日記 を含むブックマーク はてなブックマーク - SRM 466 Div1 Medium LotteryPyaterochka - chokudaiの日記 SRM 466 Div1 Medium LotteryPyaterochka - chokudaiの日記 のブックマークコメント

問題

たて5、横nの5n個のマスがあります。このうち5個があたりです。同じ行に3つあたりがあると嬉しいです。nが与えられるとき、この確率を求めなさい。n<100

方針

まぁ適当にDPすればおしまい

ソースコード

    public double chanceToWin(int N)
    {
        int i, j, k, l, m, n;
        double[,,] dp = new double[6, 6, 2]; //nokori retu flag
        for (i = 0; i < 6; i++) for (j = 0; j < 6; j++) for (k = 0; k < 2; k++) dp[i, j, k] = 0;
        dp[0, 0, 0] = 1;
        double res = 0;
        for (i = 0; i < N; i++)
        {
            for (j = 0; j < 5; j++)
            {
                double[, ,] nextdp = new double[6, 6, 2];
                double nokori = 5 * N - 5 * i - j;
                for (l = 0; l < 6; l++)
                {
                    for (m = 0; m < 6; m++)
                    {
                        for (n = 0; n < 2; n++)
                        {
                            if (dp[l, m, n] == 0) continue;
                            if (l!=5)
                            {
                                double get = (5 - l) / nokori;
                                int nextm = m + 1;
                                int nextn = n;
                                if (nextm >= 3) nextn = 1;
                                nextdp[l + 1, nextm, nextn] += dp[l, m, n] * get;
                            }
                            if (true)
                            {
                                double get = 1 - (5 - l) / nokori;
                                int nextm = m;
                                int nextn = n;
                                nextdp[l, nextm, nextn] += dp[l, m, n] * get;
                            }
                        }
                    }
                }
                dp = (double[, ,])nextdp.Clone();
            }
            for (l = 0; l < 6; l++)
            {
                for (m = 1; m < 6; m++)
                {
                    for (n = 0; n < 2; n++)
                    {
                        dp[l, 0, n] += dp[l, m, n];
                        dp[l, m, n] = 0;
                    }
                }
            }
        }
        for (l = 0; l < 6; l++)
        {
            for (m = 0; m < 6; m++)
            {
                res += dp[l, m, 1];
            }
        }
        return res;
    }
 |