実装はともかく本番にこれは思いつかないわ…。
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辺の平均から列挙する、ってのが簡単に思い浮かばない…。