Codeforces #233 Div1. C. Tree and Array

また難しいconstruction問題…。
http://codeforces.com/contest/398/problem/C

問題

整数Nが与えられるので1～Nの番号が付いた点に対し(N-1)本のコスト付辺を張り、木を作りたい。

この時、初期状態で各番号の点に対し数値T[i]=0である。
点uとvの間にコストcの辺を張ると、T[u]、T[u+1]、…、T[v]にcを加算する。

この状態で、ある点の対x,yに対し、2点間の距離d(x,y)に対し、d(x,y)=T[x]+T[x+1]…T[y]となるような対がN/2組以上出来るようにしたい。
条件を満たす(N-1)本の辺と、N/2組の点の対を答えよ。

解法

自力で解けなかったのでEditorialを見て解いた。

そもそもどういう状態だと題意を満たせるか考えてみる。
例えばuとu+1の間にコストcの辺を張ると、T[u]+T[u+1]=2*c、d(u,u+1)=cで明らかに題意を満たせない。

以下のように、たとえば1と2をより大きな数値の点を経由して結ぶようにすればよい。
3と4の間の辺のコストを大きくしてもT[1]+T[2]には影響しないので、3と4の辺のコストを増やしてd(1,2)を増やし、T[1]+T[2]と一致するようにできる。

1  2
|  |
3--4

このアイデアを発展させ、以下のように配置するとよい。

1   2   3   4
|   |   |   |
|1  |1  |1  |1
|   |   |   |
5---6---7---8
  1   3   5

こうするとd(1,2)=3、d(2,3)=5、d(3,4)=7となり(N/2-1)個の組が作れる。
1個足りない分はd(1,3)=6を利用すればよい。
Nがもっと大きくても同様にN/2個の組が作れる。

ただし、N==5の時は上記の形では題意が満たせない。
しかし最初の考え方を発展させて解くことができる。

1---2
| a |
|b  |c
|   |
3   4
    |d
    5

T[1]=a+b、T[2]=a+b+c、T[3]=b+c、T[4]=c+d、T[5]=dとなるので、以下のようにd(3,4)・d(3,5)を考える。
d(3,4)=a+b+c=T[3]+T[4]=b+2c+d
d(3,5)=a+b+c+d=T[3]+T[4]+T[5]=b+2c+2d
aは任意の値を取れるので、a=2,b=1,c=1,d=1とすればよい。

void solve() {
	int f,i,j,k,l,x,y;
	int N;
	
	cin>>N;
	
	if(N==5) {
		_P("1 2 2\n");
		_P("1 3 1\n");
		_P("2 4 1\n");
		_P("4 5 1\n");
		_P("3 4\n");
		_P("3 5\n");
		return;
	}
	
	FOR(i,N/2) _P("%d %d %d\n",i+1,i+1+N/2,1);
	for(i=N/2;i<N-1;i++) _P("%d %d %d\n",i+1,i+2,2*(i-(N/2))+1);
	FOR(i,N/2-1) _P("%d %d\n",i+1,i+2);
	_P("1 3\n");
}

まとめ

答えはあっさりだけど、本番中にこれ思いつくの難しそうだ。
本番もCなのに4名しか解答できてないらしいし…。