1277-Minimal Backgammon

問題概要

小さな一人用双六ゲームを考える．
N+1個のマスがあり，0個目が開始地点，N個目が終了時点とする．
さいころを振り出てきた目だけ駒を進める．ゴールより後に行く状態になったら逆方向に進行する．
2つの特殊なマスがあり，
L:一回休み
B:開始地点に戻る．
とする．
Tターン以内にゴールに辿りつける確率はいくつか．

解法

動的計画法
あるターンにあるマスに居る確率をしらべる．

実装(C++)

#include <algorithm>
#include <vector>
#include <iostream>
#include <iomanip>
using namespace std;

typedef long long int lli;

#define REP(i,x) for(int i=0;i<(int)(x);i++)
#define rep(i,s,x) for(int i=s;i<(int)(x);i++)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();i++)
#define RREP(i,x) for(int i=(x);i>=0;i--)
#define RFOR(i,c) for(__typeof((c).rbegin())i=(c).rbegin();i!=(c).rend();i++)
double DP[105][105];
int main(){
	int N,T,L,B;
	for(;cin>>N>>T>>L>>B;){
		if(N==0)break;
		int STATE[N+1];
		fill(STATE,STATE+N+1,0);
		REP(i,L){
			int t;
			cin>>t;
			STATE[t]=1;
		}
		REP(j,B){
			int t;
			cin>>t;
			STATE[t]=2;
		}
		REP(i,105)REP(j,105)DP[i][j]=0;
		DP[0][0]=1;
		REP(K,T+1){
			REP(i,N){
				REP(j,6){
					int next=i+j+1;
					if(next>N){
						next=N-next+N;
					}
					if(STATE[next]==2){
						next=0;
					}
					if(STATE[next]==1){
						DP[K+2][next]+=DP[K][i]*1/6.0;
					}else{
						DP[K+1][next]+=DP[K][i]*1/6.0;
					}
				}
			}
		}
		double ans=0;
		REP(i,T+1){
			ans+=DP[i][N];
		}
		cout<<setprecision(10)<<setiosflags(ios::fixed)<<ans<<endl;
	}
}