TopCoder SRM 620 Div2 Hard RandomGraph

一瞬迷ったけど何とか自力で正答。
http://community.topcoder.com/stat?c=problem_statement&pm=13143

問題

N点のグラフを考える。
各頂点間は、確率Pで無向辺が張られるとする。
グラフ中、4要素以上の連結される頂点群がある確率を求めよ。

解法

4要素以上の連結成分がない確率を求め、1から引けばよい。
状態として[3要素の連結頂点群の数][2要素の連結頂点群の数][1要素の連結頂点群の数]を持ち、頂点を順番にメモ化再帰していく。

i番目の頂点において、(i-1)番目以前の頂点と4要素以上の連結頂点群を生じないのは以下のケース。

• 以前の頂点のいずれとも辺をもたない。
• 以前の頂点のうち、2要素以下の連結頂点群1つとだけ辺をもつ。
• 以前の頂点のうち、1要素だけの連結頂点群2つとだけ辺をもつ。

補足

もっと簡単なコードの人もいるなぁ…。
SRM620 Div2Hard RandomGraph - Logfiles

class RandomGraph {
	public:
	int N;
	map<int,double> memo;
	double con[4];
	
	double dfs(int cur, int num) {
		if(cur>=N) return 1;
		int key=cur*1000000+num;
		if(memo.find(key)!=memo.end()) return memo[key];
		
		int nn[3]={num%100,num/100%100,num/10000};
		vector<int> V;
		int i,x,y;
		FOR(i,nn[0]) V.push_back(1);
		FOR(i,nn[1]) V.push_back(2);
		FOR(i,nn[2]) V.push_back(3);
		
		double ret=0;
		// pick 0
		double tp=0;
		double prob=1;
		FOR(i,V.size()) prob *= (1-con[V[i]]);
		tp=prob;
		ret += prob*dfs(cur+1,num+1);
		// pick 1
		FOR(i,V.size()) {
			double np=prob/(1-con[V[i]])*con[V[i]];
			if(V[i]==1) ret += np*dfs(cur+1,num-1+100);
			if(V[i]==2) ret += np*dfs(cur+1,num-100+10000);
		}
		// pick 2
		FOR(x,V.size()) for(y=x+1;y<V.size();y++) {
			double np=prob/(1-con[V[x]])/(1-con[V[y]])*con[V[x]]*con[V[y]];
			if(V[x]==1 && V[y]==1) ret += np*dfs(cur+1,num-2+10000);
		}
		return memo[key]=ret;
	}
	
	
	double probability(int n, int p) {
		int x,y,z;
		
		if(p==1000) return (n>=4);
		N=n;
		double P=p/1000.0;
		con[1]=1-(1-P);
		con[2]=1-(1-P)*(1-P);
		con[3]=1-(1-P)*(1-P)*(1-P);
		
		memo.clear();
		return 1-dfs(1,1);
	}
};

まとめ

頂点が4じゃなく5だとだいぶややこしくなってそうだ。