Google Code Jam 2018 Round2 : D. Gridception

少し前にInceptionを見たところだったしね。
https://codejam.withgoogle.com/2018/challenges/0000000000007706/dashboard/00000000000459f4

問題

白黒で塗られたマスで構成されたグリッドがある。
このグリッドを１回拡大すると、１マスの内容が2*2マスに拡大され、全体が縦横２倍になる。

ここであるグリッドの情報が与えられる。
このグリッドを非常に多い回数拡大したグリッドを考える。

この拡大後のグリッドの一部矩形部分を抜き出したとき、元のグリッドと同じ色のマスが最大何個連結するあるようなことがあるか。

解法

元のグリッドが

AB
CD

のような形状だとすると、何度も拡大するとこのグリッドは

AAAABBBB
AAAABBBB
AAAABBBB
AAAABBBB
CCCCDDDD
CCCCDDDD
CCCCDDDD
CCCCDDDD

のような形状になり、左右および上下の境界の位置だけをずらしたような形状となる。

よって、まず元のグリッドからA,B,C,Dの白黒の組み合わせ16通りのうちあり得るものを列挙する。
その後、この境界の位置を総当たりしつつ16通りの組み合わせを全通り試そう。

拡大後の形状と元のグリッドの形状から、元のグリッドと同じ色のマスがわかるので、Union-Findで連結させ最大要素数を求める。

int T,testcase;
int H,W;
string S[20];

int ok[2][2][2][2];
int v[20][20];

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;
	}
};

void solve(int TC) {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W;
	FOR(y,H) {
		cin>>S[y];
		FOR(x,W) S[y][x]=S[y][x]=='W';
		
	}
	
	
	if(H<=2 && W<=2) {
		_P("Case #%d: %d\n",TC,H*W);
		return;
	}
	ZERO(ok);
	FOR(y,H) FOR(x,W) {
		ok[S[y][x]][S[y][x]][S[y][x]][S[y][x]]=1;
		if(y) ok[S[y-1][x]][S[y-1][x]][S[y][x]][S[y][x]]=1;
		if(x) ok[S[y][x-1]][S[y][x]][S[y][x-1]][S[y][x]]=1;
		if(y&&x) ok[S[y-1][x-1]][S[y-1][x]][S[y][x-1]][S[y][x]]=1;
	}
	
	int ma=0;
	FOR(y,H+1) FOR(x,W+1) {
		int A[4];
		FOR(A[0],2) FOR(A[1],2) FOR(A[2],2) FOR(A[3],2) if(ok[A[0]][A[1]][A[2]][A[3]]) {
			int yy,xx;
			UF<400> uf;
			FOR(yy,H) FOR(xx,W) {
				v[yy][xx]=A[(yy>=y)*2+(xx>=x)]==S[yy][xx];
			}
			FOR(yy,H) FOR(xx,W) if(v[yy][xx]) {
				if(yy && v[yy-1][xx]) uf(yy*W+xx,(yy-1)*W+xx);
				if(xx && v[yy][xx-1]) uf(yy*W+xx,(yy)*W+xx-1);
			}
			FOR(yy,H) FOR(xx,W) if(v[yy][xx]) ma=max(ma,uf.count(yy*W+xx));
		}
	}
	
	
	_P("Case #%d: %d\n",TC,ma);
	
	
}

まとめ

Round2 Dにしてはあまり迷わない問題だった。