TopCoder SRM504.5 Div1Hard

こんな易しいDiv1Hardがあってたまるか

問題

１列に人が並んでいて、次の操作を行う。
「2人以上いるなら、サイコロを振って、4が出たら先頭の人を選ぶ。1,3,5が出たら先頭の人は一番後ろに並ぶ。2,6が出たら先頭の人は家に帰る。並んでいるのが1人だけなら、その人を選ぶ。」
最初に列にN人並んでいる。最初にM番目にいる人が選ばれる確率を求めよ。

解答

(N, M)における答えをdp[N][M]として考える。
すると、M=1のとき、dp[N][M] = 1/6 + 1/2*dp[N][N]で、M>=2のとき、dp[N][M] = 1/2*dp[N][M-1] + 1/3*dp[N-1][M-1]がわかる。
また、dp[1][1]=1.0であるから、dp[2][i]、dp[3][i]、…と順番に解いていけば良い。

コード

#include <cstdio>

class TheTicketsDivOne
{
	double dp[1001][1001];
	double tmp[1001];
	
public:
	double find(int N, int M)
	{
		dp[1][1] = 1.0;
		for(int i=2;i<=N;i++){
			tmp[1] = 1.0 / 6.0;
			for(int j=2;j<=i;j++){
				tmp[j] = dp[i-1][j-1] / 3.0;
			}
			
			double x1=tmp[1], x2=0.5;
			for(int j=2;j<=i;j++){
				x1 = (x1/2.0)+tmp[j];
				x2 = x2/2.0 + 0.5;
			}
			
			dp[i][i] = x1 / x2;
			dp[i][1] = 0.5 * dp[i][i] + tmp[1];
			for(int j=2;j<i;j++){
				dp[i][j] = 0.5 * dp[i][j-1] + tmp[j];
			}
		}
		
		return dp[N][M];
	}
};