kengo92iの日記

プログラミングとかやったことの記録を書いていきます。

AOJ-1277 : Minimal Backgammon

Problem C: Minimal Backgammon

問題名にバックギャモンと入っているが、実際は一人すごろくをやっている感じ。
サイコロを振って、出た数だけ進む。超過した分はゴールから戻る。
Loseのマスに止まると、一回休み。Backのマスに止まると、スタートに戻る。
入力された盤上の一人すごろくで、Tターン以内に上がれる確立を求めよという問題。


解法としては、動的計画法で解ける。

dp[ turn ][ pos ] = あるターンにそのマスにいる確立。 

サイコロは1〜6なので、現在の状態に(1.0 / 6.0)をかけた値を次のDPテーブルに入れれば良い。

dp[nturn][npos] += dp[turn][pos] * (1.0/6.0);  (現在の状態から1/6の確立でその状態になる)

最後は、TターンまでのNマスにいる確立を全て足したものを出力すれば良い。

//http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1277

#include<iostream>
#include<map>
#include<vector>
#include<algorithm>
#include<cmath>
#include<climits>
#include<ctime>
#include<cstring>
#include<numeric>
#include<iomanip>

#define ALL(v) (v).begin(),(v).end()
#define REP(i,p,n) for(int i=p;i<(int)(n);++i)
#define rep(i,n) REP(i,0,n)
#define dump(a) (cerr << #a << "=" << (a) << endl)
#define DUMP(list) cout << "{ "; for(auto nth : list){ cout << nth << " "; } cout << "}" << endl;

using namespace std;

const int NONE = 0;
const int LOSE = 1;
const int BACK = 2;

int N,T,L,B;
vector< vector<double> > dp; //dp[turn][pos]
vector<int> board;	

int main()
{
	cout << setiosflags(ios::fixed) << setprecision(8) << endl;

	while(cin >> N >> T >> L >> B && N)
	{
		board.assign(N+1, NONE);
		dp.assign(T+3, vector<double>(N+1,0.0));
		
		int i;
		rep(nth,L){ 
			cin >> i;
			board[i] = LOSE;
		}

		rep(nth,B){ 
			cin >> i; 
			board[i] = BACK;
		}

		dp[0][0] = 1.0;

		REP( turn, 0, T ) //現在のターン数
		{
			REP( pos, 0, N ) //現在のマス
			{
				if(dp[turn][pos] == 0.0){ continue; } //存在しないパターン
				REP( i, 1, 7 ) //サイコロを振る
				{
					int npos =  pos + i; 
					int nturn = turn + 1;
					if(npos > N){ npos = N - (npos-N); }
					if(board[npos] == LOSE){ nturn += 1; }
					if(board[npos] == BACK){ npos = 0; }
					dp[nturn][npos] += dp[turn][pos] * (1.0/6.0);
				}
			}
		}

		double ans=0;
		rep(i,T+1){
			ans += dp[i][N];
		}
		cout << ans << endl;
	}
	return 0;
}