Codeforces #422 Div2 F. Madness

これ解いてる人が少ないの、題意を把握するのが辛いからな気がする。
http://codeforces.com/contest/822/problem/F

問題

N頂点の木を成す無向グラフが与えられる。各辺の長さは1とする。
このグラフの辺を、共通部分を持たないいくつかのパスに分解したとする。(パス同士で頂点を共有するのは構わない)
各パス上で、それぞれ1個ずつ球が速度1でパス上を往復移動することを考える。

各頂点は、初期状態でタイマ値0を持ち、以後時間経過とともにタイマ値は進む。
ただし球が頂点を経由するとき、タイマはリセットさせる。

パスの切り方および球の初期位置を任意に指定できるとき、各頂点のタイマの最大値を最小化せよ。

解法

タイマの値を小さくしたいので、頂点には頻繁に球が通るようにしたい。
よって長いパスを作る意味はなく、結局1辺＝1パスとするのが良い。

タイマの最大値を最小化するには、頂点iにE[i]個辺があるとき、各辺上の球が等間隔で頂点iを通るのが良いので、2/|E[i]|ずつずれたタイミングで来るのが良い。
こう考えると、1つの辺の球の位置を決めると、あとは連鎖的に他の辺の球の位置が決まる(同じ頂点を通る他の球に対し、2/|E[i]|ずつずらしていく)。
よって適当に1辺を定めてそこからDFSで根から順に決めていけばよい。

int N;
vector<pair<int,int>> E[101];
int X[101],Y[101];
double pos[101];


void dfs(int cur,int pre,double ar) {
	int num=E[cur].size();
	int i;
	FOR(i,num) if(E[cur][i].first!=pre) {
		ar+=2.0/num;
		int x=E[cur][i].second;
		pos[x]=2-ar;
		if(Y[x]==cur) pos[x]+=1;
		while(pos[x]>=2) pos[x]-=2;
		while(pos[x]<0) pos[x]+=2;
		dfs(E[cur][i].first,cur,ar+1);
	}
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N-1) {
		cin>>X[i]>>Y[i];
		X[i]--;
		Y[i]--;
		E[X[i]].push_back({Y[i],i});
		E[Y[i]].push_back({X[i],i});
	}
	
	int num=E[0].size();
	FOR(i,num) {
		double p=i*2.0/num;
		x = E[0][i].second;
		pos[x]=p+(Y[x]==0);
		while(pos[x]>=2) pos[x]-=2;
		while(pos[x]<0) pos[x]+=2;
		
		double nex=1-p;
		if(nex<0) nex+=2;
		dfs(E[0][i].first,0,nex);
		
	}
	
	
	_P("%d\n",N-1);
	FOR(i,N-1) {
		X[i]++;
		Y[i]++;
		if(pos[i]<1) _P("%d %d %d %d %.12lf\n",1,i+1,X[i],Y[i],pos[i]);
		else _P("%d %d %d %d %.12lf\n",1,i+1,Y[i],X[i],pos[i]-1);
	}
	
}

まとめ

割と面白い問題だと思うけど、パスのくだりはなくてもよかったんじゃないかな。