バグがあったはずなのに通ってしまった。
https://community.topcoder.com/stat?c=problem_statement&pm=14468
問題
N頂点の木を成す無向グラフのうち、頂点iから最遠点までの距離がX[i]となるようなものを構成せよ。
解法
中心から外側に頂点を連結していけばよい。
X[i]の最大値、すなわち直径をDとする。
- Dが偶数の場合
- X[i]=D/2となる点iが1個ある場合、そこを中心とする。以降X[i]=(D/2+1)~(D)となる点が最低2個以上あるはずなので、それぞれ1だけX[i]が小さい点につないでいく。
- Dが奇数の場合
- X[i]=(D+1)/2となる点iが2個ある場合、その2点を結んで中心とする。以降X[i]=(D/2+2)~(D)となる点が最低2個以上あるはずなので、それぞれ1だけX[i]が小さい点につないでいく。
X[i]がD/2ないし(D+1)/2以下の点が1個でもある場合は不可なので、それは別途チェックする。
class TreeDistanceConstruction { public: vector <int> construct(vector <int> D) { vector<int> V[51]; vector<int> R; int N=D.size(); int md=0,x,i,j; FOR(i,N) V[D[i]].push_back(i), md=max(md,D[i]); int cent; if(md%2==0) { cent=md/2; if(V[cent].size()!=1) return {}; } else { cent=md/2+1; if(V[cent].size()!=2) return {}; R.push_back(V[cent][0]); R.push_back(V[cent][1]); } for(i=1;i<cent;i++) if(V[i].size()) return {}; for(x=cent+1;x<=md;x++) { if(V[x].size()<2) return {}; FOR(j,V[x].size()) { R.push_back(V[x][j]); R.push_back(V[x-1][j%V[x-1].size()]); } } return R; } }
まとめ
Codeforcesで多そうな問題。300ptだけどほとんど迷わなかった。