2014-03-05

■ CF #234 Div2 04:28

A: やるだけ

B: setを使うと簡潔にできます。問題文がちょっとおかしかったらしいですね...

C: 普通に%4%2%4してやるだけ。JOIのdragonを思い出しました

D: コスト0をuniteしてやればYes/No判定はでき、コストを求めるのはWFでよい。

E: bitごとにsetをもつ。setにはemptyな奴らの番号を入れとくとにぶたんで解ける。

ooooo 27位

ツイートする

■ SRM611 Div1 Medium 04:24

メモしときます。

基本方針は「仮平均を決め打ちし、それとの差分^2をコストとしてMSTを求め、適当に処理してから最小値をとる」

です。

次に

・なぜ仮平均を決め打ちしていいのか

・仮平均はどんな値にすれば良いのか

を考えます。

前者.

仮平均をtmp_aveとします。

MSTを作る際に使った辺のコストをc1,c2...cxとすると

sum( (tmp_ave-ci)^2 )を最小化したことになります。

ここで実際の平均をtrue_aveとすると

sum( ( (true_ave-ci) + (tmp_ave-true_ave) )^2 )

=sum( (true_ave-ci)^2 ) + 2*sum( (true_ave-ci)*(tmp_ave-true_ave) ) + sum( (tmp_ave-true_ave)^2 )

diff=(tmp_ave-true_ave)とすると

sum( (true_ave-ci)^2 ) + 2*diff*sum( (true_ave-ci) ) + sum( diff^2 )

=sum( (true_ave-ci)^2 ) + sum( diff^2 )

ここでsum( diff^2 )は定数なので

結局 (最小化したいもの+定数)を最小化できているので、これで良いと分かります。

後者.

MSTを作る過程で問題になるのは

辺の大小関係のみなので、

仮平均は全ての2辺の組の平均値+-epsを試せばよいです。O(N^4)くらいの候補になります。

結局O(N^4)の候補に対しO(N^2 log N)の操作をするので

O(N^6 log N)になりますがN<=20なのでまあ大丈夫でしょう。

一見指数か...と思わせといてこのオーダーにするところとか数式処理とか楽しかったし良問だと思います。

こういうのを本番で通せるようになるといいなあ...

コード

int par[25];
int ran[25];
void init()
{
	for(int i=0;i<25;i++) par[i]=i,ran[i]=0;
}
int find(int x)
{
	if(par[x] == x) return x;
	else return par[x]=find(par[x]);
}
void unite(int x,int y)
{
	x=find(x);
	y=find(y);
	if(x == y) return ;
	if(ran[x]else 
	{
		par[y]=par[x];
		if(ran[x] == ran[y]) ran[x]++;
	}
}
bool same(int x,int y)
{
	return find(x)==find(y);
}
double d[25][25];
class Egalitarianism2
{
	public:
	double minStdev(vector <int> x, vector <int> y) 
	{
		set<double>cand;
		int n=x.size();
		vectoredge;
		for(int i=0;ifor(int j=i+1;jdouble dx=sqrt((double)(x[i]-x[j])*(x[i]-x[j])+(double)(y[i]-y[j])*(y[i]-y[j]));
				edge.pb(mp(dx,mp(i,j)));
				d[i][j]=d[j][i]=dx;
			}
		}
		sort(edge.begin(),edge.end());
		for(int i=0;ifor(int j=i+1;jdouble a=edge[i].fi;
				double b=edge[j].fi;
				double mid=(a+b)/2.0;
				cand.insert(mid+eps); cand.insert(mid-eps); cand.insert(mid);
			}
		}
		double ret=1e12;
		for(set<double>::iterator it=cand.begin();it!=cand.end();++it)
		{
			double tmp=(*it);
			init();
			vectoredge2(0);
			for(int i=0;idouble ave=0.0,sum=0.0;
			for(int i=0;iint u=edge2[i].sc.fi; int v=edge2[i].sc.sc;
				if(!same(u,v))
				{
					unite(u,v); sum+=edge2[i].fi; ave+=d[u][v];
				}
			}
			ave/=(n-1);
			sum-=(1.0*(n-1)*(ave-tmp)*(ave-tmp));
			sum=sqrt(sum/(n-1));
			ret=min(ret,sum);
		}
		return ret;
	}
};

ツイートする