kmjp's blog

競技プログラミング参加記です

AtCoder AGC #005 : C - Tree Restoring

こちらは割とすぐ思いつけた。
http://agc005.contest.atcoder.jp/tasks/agc005_c

問題

N頂点からなる木を成す無向グラフを考える。
各辺の距離を1としたとき、各頂点iから最遠の点までの距離をA[i]とする。
条件を満たす木は存在するか。

解法

D[x] := A[i]=xとなるiの数
とする。まず距離が最長となるようなx、すなわちD[y]が正となる最大のyを求めよう。
D[y]は2以上でなければならない。また、A[i]=yとなるiを2つ(p,q)と選ぶと、それらは直径を成す。

p,qが直径を成すのであれば、その間にある点rはdist(p,r)+dist(q,r)=D[p]を満たす。
またA[r]=max(dist(p,r)+dist(q,r))である。
それに該当するA[i]が存在するか判定し、存在するならrごとに対応するA[r]を取り除こう。

あとは、p-qを結ぶ直径を成す頂点群に、残りの頂点をつないでいく。
頂点sに対し、A[s]=A[r]+1となるrが直径上に存在するなら、頂点sはそのようなrに接続すればよい。
A[r]はceil(D[y]/2)以上なので、A[s]≦ceil(D[y]/2)となるsが存在する場合、解は存在しない。

int N;
int A[101];
int num[101];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>A[i], num[A[i]]++;
	
	for(i=100;i>=0;i--) if(num[i]) {
		if(num[i]==1) return _P("Impossible\n");
		num[i]-=2;
		for(x=1;x<i;x++) {
			if(num[max(i-x,x)]==0) return _P("Impossible\n");
			num[max(i-x,x)]--;
		}
		for(x=1;x<=(i+1)/2;x++) if(num[x]) return _P("Impossible\n");
		
		
		break;
	}
	
	
	
	_P("Possible\n");
	
}

まとめ

CとDの難易度差は配点よりもずっと大きくない?