TopCoder SRM 581 Div1 Medium TreeUnion

さてDiv1 Medium。さっきのDiv2 Hardを理解していると簡単に解ける。
http://community.topcoder.com/stat?c=problem_statement&pm=12586

問題

Div2 Hardと似た問題。
TopCoder SRM 581 Div2 hard TreeUnionDiv2 - kmjp's blog

木を２つ連結し、長さKの閉路を探す。
ただし、今回は点の数Nが最大301個あることと、求めるのが最大値ではなくKの閉路の数の期待値である。

解法

KはDiv1でも7以下なので、AとBは行って帰って１往復する点は変わらない。
そこで、A内で点の組(Ai,Aj)の距離がDAとなる組の数P[DA]と、B内で点の組(Bk,Bl)の距離がDBとなる組の数Q[DB]を求める。
DA+DB+2==Kとなる(Ai,Aj)-(Bk,Bl)の組み合わせについて、Ai-BkおよびAj-Bl間を辺でつなげるか、Ai-BlおよびAj-Bk間を辺でつなげると長さKの閉路ができる。
そのため、2*P[DA]*Q[DB]だけ閉路の組み合わせができる。

各閉路が成立する確率は、AiとBkが結ばれる確率が(1/N)で、残りのAjとBlが結ばれる確率が(1/(N-1))なので、組み合わせ数をN*(N-1)で割ればよい。

class TreeUnion {
	int T,K;
	int dist[2][302][302];
	ll dd[2][5];
	public:
	string concatvec(vector <string> expr) { return accumulate(expr.begin(),expr.end(),string("")); }
	vector<int> split_int(const string &str, char delim){
		vector<int> res;
		size_t current = 0, found;
		while((found = str.find_first_of(delim, current)) != string::npos){
			string s = string(str, current, found - current);
			res.push_back(atoi(s.c_str()));
			current = found + 1;
		}
		string s = string(str, current, str.size() - current);
		res.push_back(atoi(s.c_str()));
		return res;
	}
	
	double expectedCycles(vector <string> tree1, vector <string> tree2, int K) {
		int i,j,k,x,y,z,z2;
		
		vector<int> t1=split_int(concatvec(tree1),' ');
		vector<int> t2=split_int(concatvec(tree2),' ');
		T=t1.size()+1;
		FOR(x,T) FOR(y,T) dist[0][x][y]=100;
		FOR(x,T) FOR(y,T) dist[1][x][y]=100;
		FOR(x,T) dist[0][x][x]=dist[1][x][x]=0;
		FOR(i,t1.size()) dist[0][i+1][t1[i]]=dist[0][t1[i]][i+1]=1;
		FOR(i,t2.size()) dist[1][i+1][t2[i]]=dist[1][t2[i]][i+1]=1;
		
		FOR(i,T) FOR(j,T) FOR(k,T) dist[0][j][k] = min(dist[0][j][k], dist[0][j][i]+dist[0][i][k]);
		FOR(i,T) FOR(j,T) FOR(k,T) dist[1][j][k] = min(dist[1][j][k], dist[1][j][i]+dist[1][i][k]);
		
		ZERO(dd);
		FOR(i,2) FOR(x,T) for(y=x+1;y<T;y++) {
			if(dist[i][x][y]<5) dd[i][dist[i][x][y]]++;
		}
		
		double res=0;
		for(x=1;x<=4;x++) {
			y=K-2-x;
			if(0<y && y<5) {
				res += 2*dd[0][x]*dd[1][y];
			}
		}
		
		res /= T*(T-1);
		return res;
	}
}

まとめ

Div2 Hardを解いていたおかげですぐ理解できた。
今回の木構造の与え方、珍しいな。