TopCoder SRM 843 : Div1 Hard Component

Mediumより罠は少ないかも。
https://community.topcoder.com/stat?c=problem_statement&pm=17954

問題

正整数N,Sが与えられる。
N頂点の無向グラフを考える。初期状態で辺はない。
辺が張られていない頂点対をランダムで1つ選び、辺を加える、という操作を全頂点が連結になるまで続ける。
途中、サイズSの連結成分を経由する確率を求めよ。

解法

S=1,2,Nの場合必ず経由するので1。
それ以外のケースを考える。
Nの分割について、DPの要領で分割数の少ない方から大きい方に順に確率を求めて行けばよい。

N=50だと分割数は200000近くなり、TLEしてしまう。
しかしS+1以上の連結成分のサイズは解に影響しないので、そのようなものを1つの連結成分にまとめてしまえば状態数が減り間に合うようになる。

map<vector<pair<int,int>>,double> M;
vector<vector<pair<int,int>>> C[55];

class Component {
	public:
	int S;
	void dfs(vector<pair<int,int>> V,int nex,int lef) {
		if(lef==0) {
			V=normalize(V);
			M[V]=0;
			int len=0;
			FORR2(a,b,V) len+=b;
			C[len].push_back(V);
		}
		else {
			int i;
			for(i=1;i<=min(nex,lef);i++) {
				vector<pair<int,int>> NV=V;
				NV.push_back({i,1});
				dfs(NV,i,lef-i);
			}
		}
	}
	
	vector<pair<int,int>> normalize(vector<pair<int,int>> V) {
		map<int,int> M;
		int ov=0;
		FORR2(a,b,V) {
			if(b<0) return {};
			if(b==0) continue;
			if(a>=S+1) ov+=a;
			else M[a]+=b;
		}
		V.clear();
		FORR2(a,b,M) V.push_back({a,b});
		if(ov) V.push_back({ov,1});
		return V;
	}
	
	
	double solve(int N, int S) {
		this->S=S;
		if(S<=2||N==S) return 1;
		
		M.clear();
		int i;
		FOR(i,51) C[i].clear();
		dfs({},N,N);
		M[C[1][0]]=1;
		
		int x,y;
		for(i=2;i<=N;i++) {
			FORR(V,C[i]) {
				int isS=0;
				int tpat=N*(N-1)/2;
				int sum=0;
				FORR2(a,b,V) {
					if(a==S) isS=1;
					tpat-=a*(a-1)/2*b;
				}
				if(isS) continue;
				
				double ret=0;
				FOR(x,V.size()) {
					vector<pair<int,int>> W=V;
					W[x].second--;
					W[x].second--;
					W.push_back({W[x].first*2,1});
					W=normalize(W);
					if(W.size()) {
						assert(M.count(W));
						ret+=M[W]*V[x].first*V[x].first*V[x].second*(V[x].second-1)/2;
					}
					FOR(y,x) {
						vector<pair<int,int>> W=V;
						W[x].second--;
						W[y].second--;
						W.push_back({W[x].first+W[y].first,1});
						W=normalize(W);
						if(W.size()) {
							assert(M.count(W));
							ret+=M[W]*V[x].first*V[y].first*V[x].second*V[y].second;
						}
					}
				}
				
				M[V]=ret/tpat;
				
			}
		}
		
		return 1-M[C[N][0]];
	}
}

まとめ

解法は本番思いついてたけど、最初実装で細かいミスしてたので結局0ptになってたな…。