TopCoder SRM 658 Div2 Hard OddEvenTreeHard

いい感じのアレンジ問題。
http://community.topcoder.com/stat?c=problem_statement&pm=13784

問題

基本的にはDiv1 Easyと同じ。
ただし頂点間の距離の偶奇の一部が不明である。
TopCoder SRM 658 Div1 Easy OddEvenTree - kmjp's blog

解法

不明な距離を埋めてしまえば、あとはDiv1 Easyと同様に解ける。
よって不明な距離の部分をどう埋めるか考えればよい。

Div1 Easyで出てきた条件を思い出そう。
以下が1箇所でも生じると条件を満たせない。

1. ３点x,y,zについて、D(x,y)+D(y,z)+D(z,x)が奇数。
2. 各点xについて、D(x,y)が奇数となる点yが1個もない。

よって上記が生じないように値を埋めていく。
基本的に点x,y,z(重複可)について、D(x,y), D(y,z), D(z,x)のうち2つが判明していたら残り1個を埋めればよい。
ただ、上記処理でも未確定な部分が残る場合がある。その場合、奇数で値を仮埋めして条件違反が生じないか判定し、条件違反が生じるなら偶数で埋めていけば良い。

class OddEvenTreeHard {
	public:
	
	bool valid(vector <string>& E) {
		int N=E.size();
		int x,y,z;
		
		bool up=true;
		while(up) {
			up=false;
			FOR(x,N) FOR(y,N) FOR(z,N) if(E[x][y]==-100 && E[y][z]+E[z][x]>=0) E[x][y]=E[y][z]^E[z][x], up=true;
		}
		
		FOR(x,N) FOR(y,N) FOR(z,N) if(E[x][y]+E[y][z]+E[z][x]>=0 && (E[x][y]^E[y][z]^E[z][x])==1) return false;
		return true;
	}
	
	vector <int> getTree(vector <string> E) {
		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')?1:((E[x][y]=='E')?0:-100);
		if(!valid(E)) return invalid;
		
		while(1) {
			int sx=-1,sy=-1;
			FOR(x,N) FOR(y,N) if(E[x][y]==-100 && sx==-1) sx=x,sy=y;
			if(sx==-1) break;
			
			vector<string> E2=E, E3=E;
			E2[sx][sy]=1;
			E3[sx][sy]=0;
			if(valid(E2)) E=E2;
			else if(valid(E3)) E=E3;
			else return invalid;
		}
		
		int odd=-1;
		vector<int> EE;
		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;
	}
}

まとめ

こういう感じのアレンジは割と好き。