こちらは割とすぐ思いつけた。
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の難易度差は配点よりもずっと大きくない?