AOJ 1277 : Minimal Backgammon

問題リンク：Minimal Backgammon | Aizu Online Judge

解法：
動的計画法で確率を計算した
double dp[T][N] := ターンTにマスNにいる確率　とした
初期ではdp[0][0] = 1 とする

疑似コード

for t 0..T
  for n 0..N
    for i 1..6
      dp[next_T][next_N] += dp[t][n]*(1/6.0);

答えは　dp[1..T][N]の和となる
next_Tは基本t+1(次のターン)だが、次に進む場所が'L'ならばt+2となる
next_Nはn(今いる場所)+i(サイコロで出た目)

コード：

int N,T,L,B;
double dp[MAX][MAX];
char G[MAX];

int main()
{
  while(cin >> N >> T >> L >> B,N|T|L|B)
    {
      rep(i,MAX)G[i] = '.';
      rep(i,MAX)rep(j,MAX)dp[i][j] = 0;
      rep(i,L)
	{
	  int lose;
	  cin >> lose;
	  G[lose] = 'L';
	}
      rep(i,B)
	{
	  int back;
	  cin >> back;
	  G[back] = 'B';
	}

      dp[0][0] = 1;
      rep(t,T)
	{
	  rep(n,N)//goalしたらサイコロをふる必要はないのでN-1まで
	    {
	      if(equals(dp[t][n],0))continue;
	      REP(i,1,7)
		{
		  int nextN = (n+i);
		  int nextT = t+1;
		  if(nextN > N)nextN = N - (nextN-N);
		  if(G[nextN] == 'L')nextT++; 
		  else if(G[nextN] == 'B')nextN = 0;
		  dp[nextT][nextN] += dp[t][n]*(1.0/6.0);
		}
	    }
	}
      double ans = 0;
      rep(i,T+1)ans += dp[i][N]; 
      cout << setiosflags(ios::fixed) << setprecision(10) << ans << endl;
    }
  return 0;
}