kmjp's blog

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

TopCoder SRM 704 Div1 Easy TreeDistanceConstruction

バグがあったはずなのに通ってしまった。
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だけどほとんど迷わなかった。