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; }