AOJ 1227: Minimal Backgammon

DP苦手なうえ、それに確率が加わるともう歯が立たなくなることが多い。典型問題だが、デバッグに苦労した。

問題

問題はこちら

N+1マスからなるボードがあり、Nマス目がゴールとする。はじめ0マス目に駒があり、6面の理想的なサイコロを振って出て数だけ駒を進める。駒がぴったりNマス目にたどり着いたらゴール。通り過ぎたらその分戻るとする。ボードの中には「0に戻る」マスや「1回休み」マスがいくつかある場合もある。サイコロを振れる回数をT回としたとき、T回以内にゴールできる確率を答える。

解法

素直にDPしていけばよい。dp[t][i] = (t回サイコロを振ったときにiマス目にいる確率) として値を更新していく。ゴールにたどり着いたらもはや動かないので、ゴールにたどり着ける確率は決して減らない。こういった特殊な条件（「0に戻る」や折り返し）がある場合は dp[i][j] += dp[i-1][k] よりも dp[i+1][j] = dp[i][k] といった書き方の方が処理がシンプルになってエンバグしにくいように感じる。はじめ、そのマスにたどり着ける場合の数を求めて最後に確率を求めることにしていたが、まったく合わなかった。確率係数がわかりきってる問題は素直に確率をdpの値として格納した方がいいのかもしれない。

while 1:
    N,T,L,B = map(int,raw_input().split())
    if N == 0: break
    lose = set([int(raw_input()) for i in xrange(L)])
    back = set([int(raw_input()) for i in xrange(B)])
    dp = [[0.]*(N+1) for i in xrange(T+1)]
    dp[0][0] = 1.
    p = 1./6.
    for t in xrange(T):
        for i in xrange(N):
            tt = t-1 if i in lose else t
            for j in xrange(i+1,i+7):
                if j > N: j = N-j%N
                if j in back: j = 0
                dp[t+1][j] += p*dp[tt][i]
        dp[t+1][N] += dp[t][N]
    print "%.6f"%dp[T][N]