AOJ 1277 - Minimal Backgammon

問題

0~Nまでの盤面がある双六をします。
ダイスは1~6で、確率はすべて等しいです。
スタートは0で、ゴールがNです。
ゴールを通過すると、溢れた分だけ戻ります(ゴール扱いにはなりません)。
特殊マスが2種類あり、
L : 一回休み
B: スタートへ戻る
というものが存在します。
この双六を、指定された手数以内でゴールするような確率を求めてください、というものです。
提出コード

解法

DPをします。

• dp[i][j] = iターン後に、マス目jにいるような確率

としてDPをしていきたいのですが、これだと一回休みの判定が厄介なので、

• dp[i][j][k] = iターン目に、マス目jにいるような確率(k=1なら次のターンは休み)

とすることでうまくいきます。
基本的には、
dp[i][j+(サイコロの目)][0] = dp[i-1][j][0]×(1/6) + dp[i-1][j+(サイコロの目)][1]としていけば集めることができます。
ですが、注意するポイントが3つ存在します。

(1). ゴールを通過して戻ってくるパターン
サイコロの目をxとしたときにj+xがNを超えてしまう場合、次にとまるマスは

• 2×N - j - x

となります。

(2). 一回休みのパターン
一回休みのマス目に止まったら、dp[i][j][0]ではなく、dp[i][j][1]に格納しておく必要があります。次のターンで取り出して、足し合わせます。

(3).スタートに戻るパターン
このマスに止まるパターンは、dp[i][j][0]ではなく、dp[i][0][0]に格納することで、計算を続行することができます。


あとは、dp[i][N][0]の総和を求めれば、答えとなります。