AtCoder ARC #040 : D - カクカク塗り

なかなか面白い問題でした。
http://arc040.contest.atcoder.jp/tasks/arc040_d

問題

N*Nのグリッドがあり、一部は移動不可である。
また、１マス開始位置が指定されている。

開始位置から初めて隣接マスを辿っていく。
初回は任意の隣接空きマスに移動できるが、２回目以降は直前と90度曲がった向きのマスに移動しなければならない。
同じ空きマスを２回たどることなく、全空きマスを１回ずつ通ることは可能か答えよ。

解法

以前似た問題をSRM Div2 Hardで見た気がするけど思い出せず。

各マスの移動経路を考える。
開始位置と終了位置を除くと、移動経路について各マスは左右どちらかのマスと連続し、また上下どちらかのマスと経路上で連続する。
開始位置と終了位置は上下左右どれか１マスだけと連続する。

この事から、開始位置における移動の向きと、終了位置に到達する最後の移動の向きを決めると、全体が条件を満たすか確定する。
例えば（開始位置も終了位置も含まない）ある行を考えると、上記移動経路の条件から、左から奇数番目のマスはその右隣にある偶数番目のマスと連続しなければならない。
上下も同様である。

このように考えると、移動経路は一意に決まる。
後はUnion-Find等で移動経路を連結し、全空きマスを経由するかチェックすればよい。

あとは終了位置及び開始・終了位置の移動の向きを総当たりすればよいが、そのまま全空きマスについて総当たりで上記Union-Find処理をするとO(N^4)でTLEする。
しかし上記各行・列の空きマスが基本偶数(始点・終点のところだけ調整要)でなければならないという条件があるので、そこで枝刈りすることで全体をO(N^3)で抑えることができる。

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

int N,T;
string S[1010];
int sy,sx;
int row[1010];
int col[1010];
vector<int> OR,OC;
UF<160000> uf;


bool okok(int ty,int tx,int w1,int w2) {
	int i,x,y;
	
	// 0-up/down 1-left/right
	(w1==0)?row[sy]--:col[sx]--;
	(w2==0)?row[ty]--:col[tx]--;
	
	OR.push_back(sy);
	OR.push_back(ty);
	OC.push_back(sx);
	OC.push_back(tx);

	int ng=0;
	FORR(r,OR) ng+=row[r]&1;
	FORR(r,OC) ng+=col[r]&1;
	
	OR.pop_back();
	OR.pop_back();
	OC.pop_back();
	OC.pop_back();
	(w1==0)?row[sy]++:col[sx]++;
	(w2==0)?row[ty]++:col[tx]++;
	if(ng) return false;
	
	uf.reinit();
	
	FOR(y,N) {
		FOR(x,N-1) {
			if(S[y][x]=='#' || S[y][x+1]=='#') continue;
			if(y==sy && (x==sx||(x+1)==sx) && w1==0) continue;
			if(y==ty && (x==tx||(x+1)==tx) && w2==0) continue;
			uf(y*400+x,y*400+x+1);
			x++;
		}
	}
	FOR(x,N) {
		FOR(y,N-1) {
			if(S[y][x]=='#' || S[y+1][x]=='#') continue;
			if((y==sy||(y+1)==sy) && x==sx && w1==1) continue;
			if((y==ty||(y+1)==ty) && x==tx && w2==1) continue;
			if(uf[y*400+x]==uf[(y+1)*400+x]) return false;
			uf(y*400+x,(y+1)*400+x);
			y++;
		}
	}
	
	return uf.count(sy*400+sx)==T;
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(y,N) {
		cin>>S[y];
		FOR(x,N) if(S[y][x]=='s') sy=y,sx=x,S[y][x]='.';
		FOR(x,N) if(S[y][x]=='.') row[y]++,col[x]++,T++;
	}
	FOR(i,N) if(row[i]%2) OR.push_back(i);
	FOR(i,N) if(col[i]%2) OC.push_back(i);
	if(OR.size()>2 || OC.size()>2) return _P("IMPOSSIBLE\n");
	
	FOR(y,N) FOR(x,N) if(S[y][x]=='.' && (y!=sy||x!=sx)) {
		FOR(i,2) FOR(j,2) if(okok(y,x,i,j)) return _P("POSSIBLE\n");
	}
	_P("IMPOSSIBLE\n");
}

まとめ

過去のDiv2 Hardで似た問題やっていたのだから、解けても良い問題だったな…。