AOJ 1277 - Minimal Backgammon

問題概要

N個のマスがあり、各マスにはL個の一回休みのマスと、B個のふりだしに戻るマスがある。
1〜6までの目のサイコロを降り出た目の数だけ進む。
このときTターン以内にゴールに到達するための確率を求めよ。
ただし、ゴールを超えるような目が出た場合その数だけ戻る。つまり、ちょうどゴールに到達しなければならない。

制約

• 5 ≤ N ≤ 100
• 1 ≤ T ≤ 100
• 0 ≤ L ≤ N-1
• 0 ≤ B ≤ N-1
• 1 ≤ L_i ≤ N-1
• 1 ≤ B_i ≤ N-1

解法

DPをする。
dp[i][j] := iターン目でマスjにいるときの確率

コード

#include <bits/stdc++.h>
 
using namespace std;
 
#define MAX 150
typedef pair<int,int> pii;
 
int N,T,L,B;
int arr[MAX];
 
double solve(){
  double dp[MAX][MAX];
  memset(dp,0,sizeof(dp));
  dp[0][0] = 1;
  for(int i = 1 ; i <= T ; i++){
    for(int j = 0 ; j < N ; j++){
      for(int k = 0 ; k < 6 ; k++){
        if(dp[i-1][j] == 0) continue;
        int next = j+(k+1);
        if(next > N){
          next = next - 2*(next-N);
        }
        switch(arr[next]){
        case 0:
          dp[i][next] += dp[i-1][j]/6;
          break;
        case 1:
          dp[i+1][next] += dp[i-1][j]/6;
          break;
        case 2:
          dp[i][0] += dp[i-1][j]/6;
          break;
        }
      }
    }
  }
  double res = 0;
  for(int i = 1 ; i <= T ; i++){
    res += dp[i][N];
  }
  return res;
}
 
int main(){
  int in;
  while(cin >> N >> T >> L >> B, N){
    memset(arr,0,sizeof(arr));
    for(int i = 0 ; i < L ; i++){
      cin >> in;
      arr[in] = 1;
    }
    for(int i = 0 ; i < B ; i++){
      cin >> in;
      arr[in] = 2;
    }
    printf("%.8f\n",solve());
  }
  return 0;
}