MemSQL start[c]up Round 1 : D. Reclamation

これはなかなか面白い問題だった。
http://codeforces.com/contest/325/problem/D

問題

円柱状をした星があり、初期状態はすべて海である。
この円柱の側面はR*Cの２次元グリッド状に分割できる。

ここで、グリッドのうち計N個のセルの座標が指定されるので、徐々にそのセルを土で埋めていく。
ただし、途中で「このセルを埋めると、上面と底面を海のあるセルだけで移動できなくなる」という場合、そのセルを埋める作業はスキップされる。

最終的に埋められるセル数を答えよ。

解法

Editorialを見て回答。

結局「このセルを埋めると～～」となってしまう回数を数えればよい。

そのため、R*Cを横に２つ並べてR*2Cのグリッドを生成する。
そして次に埋めるセルが(r,c)の場合、倍サイズのグリッドで(r,c)及び(r,c+C)の２か所を埋めていく。
また、隣接する８方向のセルをUnion-Findでマージしていく。
ここで、もし(r,c)と(r,c+C)を埋めるとその２セルが同じグループにマージされうる場合、これは陸地で星が１周分埋まって上面と底面が移動不可能となる。
よってそのような場合はそのセルは埋めることができない。

static const int ufmax=3000*6005;
int ufpar[ufmax],ufrank[ufmax],ufcnt[ufmax];
class UF {
	public:
	UF() { init();}
	void init(){int i; FOR(i,ufmax) { ufpar[i]=i; ufrank[i]=0; ufcnt[i]=1; } }
	int find(int x) {	return (ufpar[x]==x)?(x):(ufpar[x] = find(ufpar[x]));}
	int operator[](int x) {return find(x);}
	int count(int x) {return ufcnt[find(x)];}
	void unite(int x,int y) {
		x = find(x); y = find(y);
		if(x==y) return;
		if(ufrank[x]<ufrank[y]) ufpar[x]=y, ufcnt[y]+=ufcnt[x];
		else {ufpar[y]=x; ufcnt[x]+=ufcnt[y]; if(ufrank[x]==ufrank[y]) ufrank[x]++;}
	}
};

int H,W,N,ret;
int C[3001][6005];
UF uf;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W>>N;
	if(W==1) return _P("0\n");
	
	FOR(i,N) {
		cin>>y>>x;
		y--;x--;
		set<int> A1,A2,A3;
		
		for(int dy=-1;dy<=1;dy++) for(int dx=-1;dx<=1;dx++) {
			int ty=y+dy,tx=(x+dx+2*W)%(2*W);
			if(ty>=0 && ty<H && C[ty][tx]) A1.insert(uf[ty*6005+tx]);
			tx=(tx+W)%(2*W);
			if(ty>=0 && ty<H && C[ty][tx]) A2.insert(uf[ty*6005+tx]);
		}
		set_intersection(A1.begin(),A1.end(),A2.begin(),A2.end(),inserter(A3,A3.begin()));
		if(A3.size()) continue;
		
		ret++;
		C[y][x]=C[y][x+W]=1;
		for(int dy=-1;dy<=1;dy++) for(int dx=-1;dx<=1;dx++) {
			int ty=y+dy,tx=(x+dx+2*W)%(2*W);
			if(ty>=0 && ty<H && C[ty][tx]) uf.unite(ty*6005+tx,y*6005+x);
			tx=(tx+W)%(2*W);
			if(ty>=0 && ty<H && C[ty][tx]) uf.unite(ty*6005+tx,y*6005+x+W);
		}
	}
	cout << ret << endl;
}

まとめ

グリッドを２面分連結する発想は面白いな。
左右ループするグリッドの問題には応用できそう。