Minimal Backgammon | Aizu Online Judge
アジア地区予選2007C で出た問題

概要

（詳細は問題文を読んでください）

N+1個のマスからなる1行のゲームボードがある。0番目のマスがスタート位置で、N番目のマスがゴール位置である。
ゲームはTターンからなり、それぞれのターンで、プレイヤーは通常の六面サイコロを振り、出た目だけ進む。
このとき、ゴールで止まれずかつ進む数が余ってしまったら、その分だけゴールから戻る（e.g., N-3で5が出たらN-2に止まる）。
ゴールにたどり着いたらそこでゲームは終了する。

ただし、ボード上にはLoseマスがL個、BackマスがB個ある。
LoseマスかつBackマスは存在しない。また、スタートとゴールはLoseマスでもBackマスでもない。
Loseマスに止まると、次のターンはサイコロを振れない。
Backマスに止まると、0番目のマスに戻る。

Tターン以内にゴールにたどり着ける確率はいくらか。

制約

5 <= N <= 100
1 <= T <= 100
0 <= L,B <= N-1
1 <= L_i, B_i <= N-1
(L_i, B_iはそれぞれLoseマス、Backマスのマス番号）

解法

tターン目にn番目のマスに止まる確率 を dp[t][n] として、LoseやBack、ゴールマス、折り返しを考慮しながらDP。O(TN)。

主要部分はこんな感じ。

VVD dp(T + 1, VD(N + 1));
dp[0][0] = 1.;
rep(t, T) {
    rep(n, N) {
        if (dp[t][n] == 0) continue;

        rep(i, 6) {
            int nn = n + i + 1;
            int nt = t + 1;

            if (nn > N) nn = N - (nn - N);
            if (ts[nn] == BACK) nn = 0;
            if (ts[nn] == LOSE) ++nt;

            if (nt <= T) {
                dp[nt][nn] += dp[t][n] / 6.;
            }
        }
    }
    dp[t + 1][N] += dp[t][N];
}

return dp[T][N];

記録

AIZU ONLINE JUDGE: Code Review
34min
解法はすぐに思いついたけど、折り返しやインデックス周りでバグって時間かかった。
英語は誤読が多くて辛い。