SRM 318 DIV2 1000 SimplifiedDarts

問題

ダーツをN回投げる。毎回short rangeとlong rangeを選ぶことができる。short rangeで投げて的に当たったら2点、long rangeで投げて当たれば3点もらえる。的に当たらなかった場合は0点である。short rangeで命中させられる確率はp1、long rangeで命中させられる確率はp2である。N回投げ終わった後にW点以上得点していればプレイヤーの勝ちとする。プレイヤーが勝つ確率を求めよ。

（1 <= N <= 1000, 1 <= W <= 1000）

方針

とりあえず、DPっぽいのはすぐ分かった。毎回shortにするか、longにするかプレイヤーが最適な選択をできるというのが厄介。これをどうするか。状態をdp[残りのゲーム数][今の点数]で表すと、以下の漸化式が成り立つことに気付く。

dp[N][W] = max(shortで投げた場合ゲームに勝つ確率、longで投げた場合ゲームに勝つ確率)
              = max(p1*dp[N-1][W+2] + (1-p1)*dp[N-1][W], p2*dp[N-1][W+3] + (1-p2)*dp[N-1][W])

これでやってみる。

メモ化再帰で実装

まずメモ化で書いてみた。AC。（下のソースではやってませんが、WとP1とP2は呼び出し毎に変わる変数じゃないのでメンバー変数に入れておいた方がいいです。）

view plainprint?

1. double dp[1001][3001];  
2. class SimplifiedDarts {  
3.     double solve(int n, int p, int w, int p1, int p2) {  
4.         if (dp[n][p] >= 0) return dp[n][p];  
5.         if (n == 0) {  
6.             if (p >= w) return dp[n][p] = 1.0;  
7.             else return dp[n][p] = 0.0;  
8.         }  
9.   
10.         double ret = p1 / 100.0 * solve(n-1, p+2, w, p1, p2) + (100-p1) / 100.0 * solve(n-1, p, w, p1, p2);  
11.         ret = max(ret, p2 / 100.0 * solve(n-1, p+3, w, p1, p2) + (100-p2) / 100.0 * solve(n-1, p, w, p1, p2));  
12.   
13.         return dp[n][p] = ret;  
14.     }  
15.   
16. public:  
17.     double tryToWin(int W, int N, int P1, int P2) {  
18.         memset(dp, -1, sizeof(dp));  
19.   
20.         return solve(N, 0, W, P1, P2) * 100;  
21.     }  
22. };  

double dp[1001][3001];
class SimplifiedDarts {
    double solve(int n, int p, int w, int p1, int p2) {
        if (dp[n][p] >= 0) return dp[n][p];
        if (n == 0) {
            if (p >= w) return dp[n][p] = 1.0;
            else return dp[n][p] = 0.0;
        }

        double ret = p1 / 100.0 * solve(n-1, p+2, w, p1, p2) + (100-p1) / 100.0 * solve(n-1, p, w, p1, p2);
        ret = max(ret, p2 / 100.0 * solve(n-1, p+3, w, p1, p2) + (100-p2) / 100.0 * solve(n-1, p, w, p1, p2));

        return dp[n][p] = ret;
    }

public:
    double tryToWin(int W, int N, int P1, int P2) {
        memset(dp, -1, sizeof(dp));

        return solve(N, 0, W, P1, P2) * 100;
    }
};

DPで実装

こういう時系列でみて後ろから前に詰まっていくDPは、すぐに書けないのでDPで書き直してみる。すっきりしました。

view plainprint?

1. double tryToWin(int W, int N, int P1, int P2) {  
2.     memset(dp, 0, sizeof(dp));  
3.     FOR (i, W, 3001) dp[0][i] = 1;  
4.   
5.     FOR (i, 1, N+1) REP(j, 3*N+1) {  
6.         dp[i][j] = max(  
7.                 P1/100.0 * dp[i-1][j+2] + (100-P1)/100.0 * dp[i-1][j],    // short  
8.                 P2/100.0 * dp[i-1][j+3] + (100-P2)/100.0 * dp[i-1][j]     // long  
9.                    );  
10.     }  
11.   
12.     return dp[N][0]*100;  
13. }  

double tryToWin(int W, int N, int P1, int P2) {
    memset(dp, 0, sizeof(dp));
    FOR (i, W, 3001) dp[0][i] = 1;

    FOR (i, 1, N+1) REP(j, 3*N+1) {
        dp[i][j] = max(
                P1/100.0 * dp[i-1][j+2] + (100-P1)/100.0 * dp[i-1][j],    // short
                P2/100.0 * dp[i-1][j+3] + (100-P2)/100.0 * dp[i-1][j]     // long
                   );
    }

    return dp[N][0]*100;
}

まとめ

• 確率のDPで戦略的に次の手を選ぶことができるような問題に対して、こういうやり方はある種の定石っぽい気がする。
• DPを書くときは、base casesとSubproblem-DAGの枝の向きを意識するようにする。