AOJ-1277 : 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; }