SRM 504.5 Div2 1000pt: TheTicketsDivTwo

解法

愚直にDFSで書く。以下の実装では計算量O(2^k * n)となっているが、もちろんO(2^k)に落とせる。

int n, m, k;

double find(int _n, int _m, int _k) {
	n = _n;
	m = _m;
	k = _k;
	vector<int> tmp;
	for(int i=1; i<=n; i++){
		tmp.push_back(i);
	}
	return solve(tmp, 0);
}

double solve(vector<int> xs, int depth){
	int N = xs.size();
	if(depth == k){
		return xs[0]==m?1.0:0.0;
	}
	if(xs.size()==1){
		return xs[0]==m?1.0:0.0;
	}
	double ret = 0.0;
	ret += 1.0/6.0*(xs[0]==m?1.0:0.0);
	vector<int> tmp;
	for(int i=1; i<N; i++){
		tmp.push_back(xs[i]);
	}
	ret += 1.0/3.0*solve(tmp, depth+1);
	tmp.push_back(xs[0]);
	ret += 1.0/2.0*solve(tmp, depth+1);
	return ret;
}