解いた問題のソースコードと解説など。


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!