Facebook Hacker Cup 2017 Qualification Round, 3. Fighting the Zombie

広告

ふとTopCoder関係のカレンダーを見たらちょうどFacebook Hacker Cupをやっていたのでのぞいてみました。3がちょうど苦手なDPっぽい問題だったのと、TopCoderと違って72時間もあるから、ごはん作りながら解答を考えていて、うまく解けました。嬉しかったので図解してみます。誰かの役にたてば幸いです。

問題概要

サイコロがあります。サイコロは{4, 6, 8, 10, 12, 20}面体のどれかです。これをX回振って、Zを足したものがゾンビのHPより多ければ倒せます。倒せる確率は?

正確にはサイコロは何種類かあって最大の確率を返すとか細かい話はあるのですが、簡略化するとこんな感じです。持ってるサイコロ全部調べればいいのですから。

考え方

DP(動的計画法)で解けます。コツはn回サイコロを振ったときの合計の目mを変数として表すことです。dp[3][10]は3回サイコロを振ったときに10進んでいる確率です。図示します。

サイコロを3回振る間にゾンビを倒せるか調べるのなら、4列(0回目を考慮)の図を考えます。行数は6面体のサイコロを3回振るなら最大18(6+6+6)が出るので19行(0〜18)です。

つづいて確率を0で初期化します。

ツール使い慣れなくて位置が変ですが、続けます。

0回目、つまりまだサイコロを振っていない状態なら目の合計は0なので、dp[0][0] = 1.0にします。

0回目の列の全てのマスについて、1〜6(今は6面体で考えています)がすべて等確率で出るので、

その前の確率(1.0)を1/6ずつ右に足していきます。0回目に1である確率は0ですが、これも1/6をかけて足していきます。

図示が大変になってきたのでサボります。コードで書くのなら

        for( 全部のサイコロについて )
        {
            // 全部0で初期化する
            double dp[21][400] = {0};

            // 0回目(まだ振ってない)ときは当然合計は0なので1.0に初期化する
            dp[0][0] = 1.0;

            for( int i = 0; i < サイコロを振る回数; i++ )
            {
                for( int j = 0; j < サイコロを振る回数 * サイコロの面の数; j++ )
                {
                    for( int y = 1; y <= サイコロの面の数; y++ )
                    {
                        dp[i + 1][j + y] += dp[ i ][ j ] * 1.0 / 面の数;
                    }
                }
            }
        }

こんな感じでゴリゴリ表を埋めていきます。

最後に、一番右の列のうちゾンビのHPを超えるマスの確率を全部足していけば答えになるはずです。もし10回サイコロを振るのなら、dp[10][j]には10回目サイコロを振ったときに合計jになっている確率が入っています。もし20以上出す確率がほしければdp[10][20] + dp[10][21] .... と足していけばOKです。

補足

問題説明を端折りましたが、このダイスは6面体のダイスを4回振って10引くみたいな処理をすることがあります。逆に最後に10足すようなこともあります。もしこの足される数値ZがゾンビのHPを超えていれば計算するまでもなく1.0が答えになります。私はここの箇所を間違えまして、気づいたときにはあとのまつりだったのですが、苦手なDPの問題を少し考えて自力で答えを出せたので満足しています。

広告