AtCoder ARC #103 : F - Distance Sums

今回やたらとConstructionゲーだ。
https://beta.atcoder.jp/contests/arc103/tasks/arc103_d

問題

1～Nのラベル付きのN頂点からなる木を成す無向グラフを考える。
各頂点に対し、そこから全頂点への距離の総和D[i]が与えられる。
D[i]はすべて異なる。
この時、条件を満たすグラフを構築せよ。

解法

Dが昇順だとする。（そうでない場合、とりあえず昇順に並べ替えてあとでラベルを変えればよい）
1番の頂点は大よそ重心あたりに来そうというのはわかる。
それ以外の頂点について、より小さな番号の頂点につながらなければならない。
また、そのような頂点は常にひとつである（そうしないと1番が唯一の「より小さな番号の頂点」がない点とならない）

よって、大きなラベルから順につながる先の小さな番号の頂点を探そう。
これを、1番の頂点とした根付き木において親を探す処理だと考える。

今頂点vを考えるとき、SubTree(v)中の頂点数をC(v)とする。
親頂点がuのとき、D[u] = D[v]-(N-2C(v))となる。よって、DがdistinctなためDの二分探索でuを求められる。

こうしてvの親頂点を探したら、最後に生成された木についてDを実際に計算して検算しよう。

int N;
ll D[101010];
pair<ll,int> P[101010];
int num[101010],par[101010];
ll DS[101010];
vector<pair<int,int>> E;
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>D[i];
		P[i]={D[i],i+1};
	}
	sort(P,P+N);
	sort(D,D+N);
	
	for(i=N-1;i>=1;i--) {
		num[i]++;
		ll sj=D[i]+2*num[i]-N;
		x=lower_bound(D,D+N,sj)-D;
		if(x>=i || D[x]!=sj) return _P("-1\n");
		E.push_back({x,i});
		num[x]+=num[i];
		DS[x]+=DS[i]+num[i];
		par[i]=x;
	}
	if(DS[0]!=D[0]) return _P("-1\n");
	
	FORR(e,E) cout<<P[e.first].second<<" "<<P[e.second].second<<endl;
}

まとめ

今回出てたらDEF落としてそう…。