TopCoder SRM 562 Div2 Hard RandomOption

続いてDiv2 Hard。
900ptということでDiv1 Mediumよりは簡単。
http://community.topcoder.com/stat?c=problem_statement&pm=12315

問題文を見ると音ゲーっぽい文面が色々あるけど、本題にはあまり関係ない。
いくつかのレーンを１列にランダムに並べるとき、隣接できないレーンがある場合に問題ないレーン構成ができる確率を求める。

解法としては再帰処理をしている。たぶんDPでも解けるね。
左から順にレーンを並べていって、残りの列の並べ方の成立する確率の平均値を求めていく。
状態数としては、すでに並べ終わった列のビットマスクと、現在一番右端のレーンの番号なのでO(N*2^N)程度。
N<=14なのでなんとか解けた。

class RandomOption {
	public:
	double val[17000][15];
	int ng[17][17];
	int K;
	
	double calc(int mask, int right) {
		int i,c;
		double t;
		
		if(right!=-1 && val[mask][right]!=-1) return val[mask][right];
		
		c = 0;
		t = 0;
		FOR(i,K) {
			if(mask & (1<<i)) continue;
			c++;
			if(right==-1 || !ng[right][i]) t += calc(mask | (1<<i),i);
		}
		
		if(c==0) val[mask][right] =  1;
		else val[mask][right] = t/c;
		return val[mask][right];
	}
	
	double getProbability(int keyCount, vector <int> badLane1, vector <int> badLane2) {
		int x,y;
		K=keyCount;
		
		FOR(x,15) FOR(y,17000) val[y][x]=-1;
		ZERO(ng);
		FOR(x,badLane1.size()) ng[badLane1[x]][badLane2[x]]=ng[badLane2[x]][badLane1[x]]=1;
		return calc(0,-1);
	}

};

まとめ

Div2とはいえHardの割に簡単な問題。
最初音ゲー譜面のパースをさせられるかと思った。