TopCoder SRM 611 Div1 Medium Egalitarianism2

実装はともかく本番にこれは思いつかないわ…。
http://community.topcoder.com/stat?c=problem_statement&pm=13008

問題

2次元座標上にN個の点が与えられるので、(N-1)本の辺を張って全域木を作りたい。
この時、(N-1)本の辺の長さの標準偏差を最小化せよ。

解法

(N-1)本の辺の長さをL[i]、平均をAとすると、を最小化したい。

ここである2辺L[i]とL[j]があってそのうち1本だけを使う場合、どちらを選択するとよいかは当然Aと近い方を選択したい。
すなわち、Aが(L[i]+L[j])/2より大きいかどうかで使う辺が変わる。

よって、全部の辺N*(N-1)/2本から2本抜き出して平均を取り、Aの候補とする。
各Aの候補について、辺のコストをとして最小全域木を作ったうえで、選んだ辺を用いて再度平均値及び標準偏差を求め、最小値を更新していけばよい。

class UF {
	public:
	static const int ufmax=22;
	int ufpar[ufmax],ufrank[ufmax];
	UF() { init();}
	void init(){int i; FOR(i,ufmax) { ufpar[i]=i; ufrank[i]=0; } }
	int find(int x) {	return (ufpar[x]==x)?(x):(ufpar[x] = find(ufpar[x]));}
	int operator[](int x) {return find(x);}
	void unite(int x,int y) {
		x = find(x); y = find(y);
		if(x==y) return;
		if(ufrank[x]<ufrank[y]) ufpar[x]=y;
		else {ufpar[y]=x; if(ufrank[x]==ufrank[y]) ufrank[x]++;}
	}
};

class Egalitarianism2 {
	int N;
	double dist[21][21];
	ll distsq[21][21];
	public:
	double mst(double ave) {
		int x,y;
		vector<pair<double,int> > V;
		FOR(x,N) FOR(y,N) if(x<y) V.push_back(make_pair((ave-dist[x][y])*(ave-dist[x][y]),x*100+y));
		sort(V.begin(),V.end());
		
		UF uf;
		double nave=0;
		ll sum=0;
		ITR(it,V) {
			int k1=it->second/100;
			int k2=it->second%100;
			if(uf.find(k1)==uf.find(k2)) continue;
			nave+=dist[k1][k2];
			sum+=distsq[k1][k2];
			uf.unite(k1,k2);
		}
		nave/=N-1;
		return sqrt(sum/(double)(N-1)-nave*nave);
	}
	
	double minStdev(vector <int> x, vector <int> y) {
		int i,j;
		vector<double> cand;
		N=x.size();
		
		FOR(i,N) FOR(j,N) distsq[i][j]=(x[i]-x[j])*(ll)(x[i]-x[j])+(y[i]-y[j])*(ll)(y[i]-y[j]);
		FOR(i,N) FOR(j,N) if(i!=j) cand.push_back(dist[i][j]=sqrt(distsq[i][j]));
		double ret=1e20;
		FOR(i,cand.size()) FOR(j,cand.size()) if(i>=j) {
			ret=min(ret,mst((cand[i]+cand[j])/2.0));
		}
		return ret;
	}
};

まとめ

平均値の候補を2辺の平均から列挙する、ってのが簡単に思い浮かばない…。