AOJ1277 Minimal Backgammon

問題リンク Minimal Backgammon

• 概要

0〜NマスのBackgammonをする。0がスタート地点でNがゴールである。サイコロを振って出た目の数だけ進む。ゴールを飛び越す場合、超過分だけマスを戻る。マスにはloseマスとbackマスがある。loseマスは停まると1ターン休み、backマスは停まるとスタート地点に戻る。このゲームをTターン以内にクリアする確率を求めよ。1つのマスにloseマスとbackマスが同時に存在することはない。
5 <= N <= 100
1 <= T <= 100

• 解法

DPで解けます。
dp[i][j]: iターン目にマスjに停まる確率
を更新します。dp[0][0] = 1.0と初期化しておきます。
loseマスに停まった場合、i+2ターン目にマスjに停まったと処理します。
backマスに停まった場合、マス0に停まったと処理します。

• ソース

import java.util.Scanner;

//Minimal Backgammon
public class AOJ1277 {

	void run(){
		Scanner sc = new Scanner(System.in);
		for(;;){
			int n = sc.nextInt(), T = sc.nextInt(), l = sc.nextInt(), b = sc.nextInt();
			if((n|T|l|b)==0)break;
			boolean[] lose = new boolean[n+1];
			for(int i=0;i<l;i++)lose[sc.nextInt()] = true;
			boolean[] back = new boolean[n+1];
			for(int i=0;i<b;i++)back[sc.nextInt()] = true;
			double[][] p = new double[T+1][n+1];
			p[0][0] = 1.0;
			for(int t=0;t<T;t++)for(int i=0;i<=n;i++){
				if(i==n){
					p[t+1][n] += p[t][n]; continue;
				}
				for(int j=1;j<=6;j++){
					double dt = p[t][i]/6.0;
					int next = i+j;
					if(n<next){
						int d = next-n;
						next = n-d;
					}
					if(lose[next]){
						if(t+2<=T)p[t+2][next] += dt;
					}
					else if(back[next]){
						p[t+1][0] += dt;
					}
					else p[t+1][next] += dt;
				}
			}
			System.out.printf("%.6f\n", p[T][n]);
		}
	}
	
	public static void main(String[] args) {
		new AOJ1277().run();
	}
}