TopCoder SRM 658 Div1 Easy OddEvenTree

Easyが少し遅く、Mediumは枝刈り不足でTLEのためレート減少。
http://community.topcoder.com/stat?c=problem_statement&pm=13759

問題

N頂点からなる木を成すグラフを作りたい。
ここで頂点間の最短経路における経由する辺の数の偶奇が与えられる。

条件を満たすグラフが作成可能なら一例を答えよ。

解法

２点x,y間の距離のパリティをD(x,y)とする。
まず条件を満たさないケースを排除する。

以下の条件では条件を満たさない。

• 各点xについて、D(x,x)が奇数。
• ２点x,yについて、D(x,y)とD(y,x)が不一致。
• ３点x,y,zについて、D(x,y)+D(y,z)+D(z,x)が奇数。
• 各点xについて、D(x,y)が奇数となる点yが1個もない。

上３つについては、実は３つ目の条件でx,y,zに重複を許可すると、これ1個でまとめて判定で来て楽。

ここまで来ると条件を満たせることは確実なので、後はどう木を構築するかが問題。
本番自分が取った解法と、他のより簡単な解法を紹介。

全域木の構築

Union-Find等を用いて頂点の連結状態を管理する。
２点x,yが非連結かつ以下の条件を満たすなら、そこに辺を張る。

• 各点zについて、D(x,z)とD(y,z)のどちらかが奇数でどちらかが偶数。

もし上記条件を満たすなら、経路z→x上にyが来るか経路z→y上にxが来るかのどちらかと考えて矛盾が生じないためである。
上記処理を全頂点が連結するまで続ける。

中心の２点に他の点を接続する

こちらの方が実装は容易。
頂点0に対し、D(0,x)が奇数となる点xを1個選んで0-xに辺を張る。
残りの点yは、上記条件によりD(0,x)が奇数なのでD(0,y)とD(x,y)のどちらかは奇数でどちらかが偶数となる。
よってyは奇数となる側の頂点との間に辺を張ればよい。

以下のコードは後者。
10行ちょいで書けるね。

class OddEvenTree {
	public:
	vector <int> getTree(vector <string> E) {
		vector<int> EE;
		vector<int> invalid(1,-1);
		int x,y,z,i;
		int N=E.size();
		
		FOR(x,N) FOR(y,N) E[x][y]=(E[x][y]=='O');
		FOR(x,N) FOR(y,N) FOR(z,N) if((E[x][y]+E[y][z]+E[z][x])%2==1) return invalid;
		
		int odd=-1;
		FOR(i,N) if(E[0][i]==1) odd=i, EE.push_back(0),EE.push_back(i);
		if(odd==-1) return invalid;
		for(i=1;i<N;i++) if(E[0][i]==0) EE.push_back(odd),EE.push_back(i);
		
		return EE;
	}
}

まとめ

チャレンジフェーズでは多くの人が後者のアプローチだった。
自分は無駄に前者で頑張ってタイムロスしたけど、これ定番テクなのかな？