AOJ2134 Deadly Dice Game

問題リンク Deadly Dice Game

• 概要

長さNの円形のボードがある。ボードの各マスは黒色か赤色である。
初期位置を任意に選ぶことができる。サイコロを振って出た目の数だけ時計回りに進む。サイコロをT回振ったとき最終的に赤色のマスに停まる確率の最大値を答えよ。
1 <= N <= 2000
1 <= T <= 2000

• 解法

DPです。
dp[i][j]: マスiにいて、サイコロを残りj回振った後赤色に停まる確率
という表を埋めれば解けます。気をつけることは特にないと思います。

• ソース

import java.util.Scanner;

//Deadly Dice Game
public class AOJ2134 {

	void run(){
		Scanner sc = new Scanner(System.in);
		for(;;){
			int n = sc.nextInt(), T = sc.nextInt();
			if((n|T)==0)break;
			char[] a = sc.next().toCharArray();
			double[][] dp = new double[n][2];
			for(int i=0;i<n;i++)dp[i][0]=a[i]=='R'?1:0;
			int x = 1;
			for(int t=1;t<=T;t++,x=1-x)for(int i=0;i<n;i++){
				double p = 0;
				for(int k=1;k<7;k++)p+=dp[(i+k)%n][1-x]/6;
				dp[i][x] = p;
			}
			double res = 0;
			for(int i=0;i<n;i++)res= Math.max(res, dp[i][1-x]);
			System.out.printf("%.9f\n", res);
		}
	}
	
	public static void main(String[] args) {
		new AOJ2134().run();
	}
}