HOJ 1237 - Swap Game
問題概要
三面サイコロと3つのカップがある。
サイコロの各面には1,2,3の整数が書かれており、サイコロを振ったとき1が書かれた面が上になる確率は$ \ A \ $、2は$ \ B \ $、3は$ \ C \ $である。
はじめ$ \ P \ $番目のカップにのみボールが入っており、サイコロを$ \ K \ $回振り以下の操作を行う。操作が全て終わった後に$ \ R \ $番目のカップにボールが入っている確率を求めよ。
- 1が書かれた面が上ならばカップ1とカップ2の中身を入れ替える
- 2が書かれた面が上ならばカップ2とカップ3の中身を入れ替える
- 3が書かれた面が上ならばカップ1とカップ3の中身を入れ替える
制約
- $0 \leq K \leq 10^5$
- $1 \leq P,R \leq 3$
- $0 \leq A,B,C \leq 1$
- $A + B + C = 1$
解説
動的計画法で答えを求めます。
$i \ $回目の操作でボールが$ \ j \ $番目のカップに入っている確率を$ \ dp[i][j] \ $とします。
$ dp[i][j] \ $は「$ \ j \ $番目のカップからボールが移動しない確率 + 他のカップからボールが移動してくる確率」で求められるので、
- $dp[i][1] = dp[1][i - 1] \times B + dp[2][i - 1] \times A + dp[3][i - 1] \times C$
- $dp[i][2] = dp[1][i - 1] \times A + dp[2][i - 1] \times C + dp[3][i - 1] \times B$
- $dp[i][3] = dp[1][i - 1] \times C + dp[2][i - 1] \times B + dp[3][i - 1] \times A$
というように求められます。
これを$ \ dp[1] \ $から順番に求め、$dp[K][R] \ $を出力すればよいです。
