SRM 504.5 Div2 Hard TheTicketsDivTwo
問題
http://apps.topcoder.com/stat?c=problem_statement&pm=11433&rd=14514
n人の人間が一列に並んでいる。サイコロをふり、4が出たら列の先頭に並んでいる人を選んでおしまい。それ以外の偶数が出たら先頭の人を列から外して、もう一回サイコロを振る。奇数が出たら先頭の人を列の最後尾に配置して、もう一度サイコロを振る。もしサイコロをk回振った後に人が選ばれていなければ、列の先頭の人を選んで終了。開始時点の列でm番目に並んでいた人が選ばれる確率を求めよ。
1 <= m <= n <= 10, 1 <= k <= 10
やりかた
いろいろなものを参考にしました。。
全状態は6^10≒60000000以下なので全て列挙することはできる。なので深さ優先探索で全状態を列挙する事ができる。
- 列の人数が一人になる(n == 1)まで状態が続いているなら、それは最初m番目にいた人間が残っているということ(それ以外の時は探索を打ち切っている)なので確率1.0を返す。
- またk回の試行の後に最初にm番目にいた人間が先頭に来ていたら1.0、そうでなければ0.0を返す。
- そして最初にm番目にいた人間が先頭にいるときには1/6の確率でその時点で選ばれる。その時点で選ばれないときにも奇数が出れば(確率1/2)その人を最後尾に回して、試行を一回進めて再びサイコロを振る。
- これ以外の状況では奇数が出て(確率1/2)列を一つローテーションして次フェーズ、もしくは4以外の偶数が出て(確率1/3)人数を一つ減らして次フェーズに移る
とやることで答えを求めることができる。
以下ソース。
class TheTicketsDivTwo { public: double rec(int n, int m, int k){ if(n == 1) return 1.0; if(k == 0) return m == 1 ? 1.0 : 0.0; if(m == 1) return 1 / 6.0 + rec(n, n, k - 1) / 2.0; return rec(n, m - 1, k - 1) / 2.0 + rec(n - 1, m - 1, k - 1) / 3.0; } double find(int n, int m, int k) { return rec(n, m, k); } };
勉強のつもりで動的計画法で書き直す。
class TheTicketsDivTwo { public: double find(int n, int m, int k) { double dp[20][20][20]; memset(dp, 0, sizeof(dp)); for(int i = 1; i <= k; i++) dp[1][1][i] = 1.0; for(int i = 1; i <= n; i++) dp[i][1][0] = 1.0; for(int l = 1; l <= k; l++){ for(int i = 2; i <= n; i++){ dp[i][1][l] = 1 / 6.0 + dp[i][i][l - 1] / 2.0; for(int j = 2; j <= i; j++){ dp[i][j][l] = dp[i][j - 1][l - 1] / 2.0 + dp[i - 1][j - 1][l - 1] / 3.0; } } } return dp[n][m][k]; } };
SRM 500に入って動的計画法が増えてきたように思う。もともとDPを訓練したくてDiv2Hをやっているので嬉しいが、解けないのでちょっとつらい。
Get up! 明日のSUPER ST@R!