TopCoder SRM 645 Div2 Hard JanuszInTheCasino

変な問題？想定解これでいいのかな…。
http://community.topcoder.com/stat?c=problem_statement&pm=13349

問題

初期状態でN人のプレイヤーが、以下のゲームをKターン行う。

• 各プレイヤーはM個のフィールドを１つ選択する。
• フィールドのうち１つが等確率で選択され、選択されたフィールドを選択したプレイヤーは敗退する。

Kターン後、１人でもプレイヤーが残れば、全員がゲームの勝者となる。
プレイヤー群が最適な戦略を取るとき、全体がゲームの勝者となる確率を求めよ。

解法

各ターンで残りプレイヤー数をp人とすると、p人をM個のフィールドに均等に分ければよい。
選択されたフィールドにより、ceil(p/M)人ゲームオーバーになる場合と、floor(p/M)人ゲームオーバーになる場合があるが、それぞれK回再帰しながら探索すればよい。

ceilを取る場合とfloorを取る場合で、各ターンでの残存人数はそんなに変化しないので、状態が爆発したりはしない。

map<ll,double> memo[51];

class JanuszInTheCasino {
	public:
	int M,K;
	
	double dodo(ll n,int k) {
		if(n<=0) return 0;
		if(k==0) return 1;
		if(memo[k].count(n)) return memo[k][n];
		double ret=0;
		
		if(n%M==0 || k<K-50) ret=dodo(n-n/M,k-1);
		else {
			ret=dodo(n-n/M,k-1)*(M-n%M)/M + dodo(n-(n/M+1),k-1)*(n%M)/M;
		}
		
		return memo[k][n]=ret;
	}
	
	double findProbability(long long n, int m, int k) {
		int i,j;
		FOR(i,51) memo[i].clear();
		M=m;
		K=k;
		return dodo(n,k);
	}
}

まとめ

誤差の許容量が多いので、モンテカルロでシミュレーションしても通るらしい？