TopCoder SRM 685 Div2 Hard RGBTree

Div1 Mediumより苦戦した。
https://community.topcoder.com/stat?c=problem_statement&pm=14192

問題

N頂点からなる無向グラフが与えられる。
このグラフは自己ループや多重辺を持たない。
また、各辺は赤青緑のいずれかで塗られている。

この無向グラフに対して全域木を作りたい。
その際、赤青黄の辺を同じ数ずつ使った全域木は構築可能か判定せよ。

解法

m=(N-1)/3とすると、各色の辺はm本ずつ使うことになる。
あとはUnion-Findを用いて連結状態を管理しつつ、各色のうち非連結な頂点群を結ぶ辺をm本ずつ求めるべくDFSで枝刈りしながら探索すればよい。

なおこのままだと一部のテストケースでTLEするので、自分は下記の最適化を行った。

• 3つ目の色については、用いるm本は一意に決まる。すなわち非連結な頂点対を結ぶ辺を順に選択すればよい。よって3つめの色はDFSによる分岐は必要ない。
• 上記改善により、3色目の処理は高速に行える。よって赤青黄のうち一番辺の数の多い色を3つめに処理するようにする。

他の回答を見ると、bitdpに持ち込む手法もあるようだ。

template<int um> class UF {
	public:
	vector<int> par,rank,cnt;
	UF() {par=rank=vector<int>(um,0); cnt=vector<int>(um,1); for(int i=0;i<um;i++) par[i]=i;}
	void reinit() {int i; FOR(i,um) rank[i]=0,cnt[i]=1,par[i]=i;}
	int operator[](int x) {return (par[x]==x)?(x):(par[x] = operator[](par[x]));}
	int count(int x) { return cnt[operator[](x)];}
	int operator()(int x,int y) {
		if((x=operator[](x))==(y=operator[](y))) return x;
		cnt[y]=cnt[x]=cnt[x]+cnt[y];
		if(rank[x]>rank[y]) return par[x]=y;
		rank[x]+=rank[x]==rank[y]; return par[y]=x;
	}
};


class RGBTree {
	public:
	int N,ok;
	vector<pair<int,int>> E[3];
	
	void dfs(UF<13>& uf,int ph,int d,int l) {
		int i;
		
		if(d==E[ph].size()) {
			if(l) return;
			if(ph==1) {
				l=(N-1)/3;
				FOR(i,E[2].size()) if(l>0 && uf[E[2][i].first]!=uf[E[2][i].second]) {
					l--;
					uf(E[2][i].first,E[2][i].second);
				}
				if(uf.count(0)==N) ok=1;
			}
			else {
				dfs(uf,ph+1,0,(N-1)/3);
			}
			return;
		}
		
		if(l>0 && uf[E[ph][d].first]!=uf[E[ph][d].second]) {
			UF<13> uf2=uf;
			uf2(E[ph][d].first,E[ph][d].second);
			dfs(uf2,ph,d+1,l-1);
			if(ph==2) return;
		}
		dfs(uf,ph,d+1,l);
	}
	
	
	string exist(vector <string> G) {
		int x,y;
		N=G.size();
		FOR(x,3) E[x].clear();
		FOR(y,N) FOR(x,y) {
			if(G[y][x]=='R') E[0].push_back({x,y});
			if(G[y][x]=='G') E[1].push_back({x,y});
			if(G[y][x]=='B') E[2].push_back({x,y});
		}
		if(E[0].size()>E[1].size()) swap(E[0],E[1]);
		if(E[1].size()>E[2].size()) swap(E[1],E[2]);
		if(E[0].size()>E[1].size()) swap(E[0],E[1]);
		ok=0;
		UF<13> uf;
		dfs(uf,0,0,(N-1)/3);
		if(ok) return "Exist";
		return "Does not exist";
		
	}
}

まとめ

自分の方法はちょっと強引だし、bitdpが想定解だったりするのかなぁ…。