Google Code Jam 2019 Round 3 : C. Datacenter Duplex

言われると簡単なんだよな…。
https://codingcompetitions.withgoogle.com/codejam/round/0000000000051707/0000000000158f1c

問題

グリッド状の各セルがA,Bで塗り分けられている。
同じ色のセル同士を配線でつなぎ、同じ色のセルはすべて連結となるようにしたい。
隣接するセルは無条件で配線をつなぐことができる。

また、加えて条件付きで斜め方向にも配線を加えることができる。
以下の位置関係にある４セルを考える。
X-X間とY-Y間のいずれか一方だけ配線が可能である。

XY
YX

同じ色のセルをすべて配線で連結できるか。
できるならその例を示せ。

解法

まず隣接セルはUnion-Findで連結させてしまおう。
その後だが、実は貪欲法でよい。
上のようなケースにおいて、A-AかB-Bの関係のうち、連結でないものがあれば貪欲にどっちでもいいので選んでしまってよい。

int T;
int H,W;
string S[101];
char U[101][101];
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;
	}
};
UF<10101> uf;

void solve(int _loop) {
	int f,i,j,k,l,x,y;
	
	cin>>H>>W;
	FOR(y,H) cin>>S[y];
	uf.reinit();
	FOR(y,H) FOR(x,W) {
		if(y && S[y][x]==S[y-1][x]) uf(y*100+x,(y-1)*100+x);
		if(x && S[y][x]==S[y][x-1]) uf(y*100+x,y*100+x-1);
	}
	ZERO(U);
	FOR(y,H-1) FOR(x,W-1) U[y][x]='.';
	FOR(y,H-1) FOR(x,W-1) if(S[y][x]==S[y+1][x+1] && S[y+1][x]!=S[y][x] && S[y][x+1]!=S[y][x]) {
		if(uf[y*100+x]!=uf[(y+1)*100+x+1]) {
			U[y][x]='\\';
			uf(y*100+x,(y+1)*100+x+1);
		}
		else if(uf[(y+1)*100+x]!=uf[y*100+x+1]) {
			U[y][x]='/';
			uf((y+1)*100+x,y*100+x+1);
		}
	}
	
	
	int num=0;
	FOR(y,H) FOR(x,W) if(uf[y*100+x]==y*100+x) num++;
	if(num==2) {
		_P("Case #%d: POSSIBLE\n",_loop);
		FOR(y,H-1) _P("%s\n",U[y]);
	}
	else {
		_P("Case #%d: IMPOSSIBLE\n",_loop);
	}
	
	
	
	
}

まとめ

うーん、本番無駄に二部グラフとか色々考えちゃったんだよな。