TopCoder SRM 504.5 Div2 Hard TheTicketsDivTwo

SRM504.5ってなんだろ。SRM504がunratedだった？
http://community.topcoder.com/stat?c=problem_statement&pm=11433

問題

初期状態で1～Nの人が並んでいる。
この状態でサイコロを振り、１人人を選ぶ。
サイコロを振ったときは以下のように処理する。

• 4が出たら列の先頭の人を選んで終了。
• 1,3,5が出たら列の先頭の人を末尾に移動して継続。
• 2,6が出たら先頭の人を列から外して継続。

途中で４が出て１人選ぶか、列が残り１人になるか、K回サイコロを振った時点で処理は終了する。
K回サイコロを振って列に人が残ってたら、先頭の人を選ぶ。

M番目の人が選ばれる確率を求めよ。

解法

１回サイコロを振ると３通りのパターンがある。
最大でK<=10回しかサイコロを振らないので、3^10通り総当たりするだけ。

class TheTicketsDivTwo {
	int pat;
	int N,M,K;
	int hist[11];
	
	public:
	void dfs(int cur,int npat,vector<int>& v) {
		int i,j,g=1;
		
		for(i=cur;i<K;i++) g*=6;
		if(cur==K) {
			if(v[0]==M) pat+=npat;
		}
		else if(v.size()==1) {
			if(v[0]==M) pat+=npat*g;
		}
		else {
			vector<int> v2;
			//4
			if(v[0]==M) pat+=npat*g/6;
			v2=v;
			v2.erase(v2.begin());
			//2,6
			dfs(cur+1,npat*2,v2);
			//1,3,5
			v2.push_back(v[0]);
			dfs(cur+1,npat*3,v2);
		}
	}
	
	double find(int n, int m, int k) {
		int i;
		pat=0;
		N=n;M=m;K=k;
		vector<int> V;
		FOR(i,N) V.push_back(i+1);
		dfs(0,1,V);
		double ret=pat;
		FOR(i,k) ret/=6.0;
		return ret;
	}
};

まとめ

Div2 Hardとはいえだいぶ簡単なような。