Codeforces #293 Div2 F. Pasha and Pipe

実装問題寄りかな。
http://codeforces.com/contest/518/problem/F

問題

N*Mの2次元グリッドがあり、一部のセルが埋まっている。
ここに以下の条件を満たすようにパイプを通したい。

• パイプは太さ1セルの線である
• パイプは埋まってないセルのみ通すことができる
• グリッドの角のセルは利用不可
• パイプの両端は異なる周辺に接している
• パイプの通ったセルは周辺部以外2セルと接している
• パイプは最大2回まで90度曲げることができる

条件を満たすパイプの通し方の組み合わせを答えよ。

解法

事前に横方向および縦方向の累積和を取ることで、連続した横方向のセル列または縦方向のセル列に対し、埋まったセルの有無をO(1)で判定できる。
これを用いて、曲げる回数ごとにパイプの通し方を列挙する。

曲がらないケース

左右端の間に埋まったセルがない行、および上下端の間に埋まったセルがない列の数を求めればよい。

1回曲がるケース。

曲がるセルを(周辺部を除いた)全セル総当たりする。

そのセルから(上端及び左端)、(上端及び右端)、(下端及び左端)、(下端及び右端)それぞれに埋まったセルを通らず到達できる数を求めればよい。

2回曲がるケース。

開始と終了時は縦方向にパイプを通し、1回目と2回目曲がる間は左右にパイプを通すケースを考える。
左右移動の間、(x1,y)-(x2,y)の間が埋まっておらずパイプが通せるとする。(x1＜x2）
この時、以下の条件を満たせば2回パイプを曲げて上下端を端とするパイプの通し方ができる。

1. (x1,y)から上端までパイプが通せ、(x2,y)から下端までパイプが通せる
2. (x1,y)から下端までパイプが通せ、(x2,y)から上端までパイプが通せる
3. (x1,y)から上端までパイプが通せ、(x2,y)から上端までパイプが通せる。かつx1+1＜x2
4. (x1,y)から下端までパイプが通せ、(x2,y)から下端までパイプが通せる。かつx1+1＜x2

(x1,y)、(x2,y)を総当たりするとO(H*W^2)かかって間に合わない。
しかし以下のような累積和S[i][x]を使うと、上記処理をO(HW)で済ませることができる。

• S[0][x]＝(x,y)からパイプを通すことができる下限を(xm,y)としたとき、(xm,y)～(x,y)の各点から上端にパイプを通せる数。
• S[1][x]＝(x,y)からパイプを通すことができる下限を(xm,y)としたとき、(xm,y)～(x,y)の各点から下端端にパイプを通せる数。

開始と終了時は横方向にパイプを通し、1回目と2回目曲がる間は上下にパイプを通すケースも同様に考えればよい。

int H,W;
string A[2020];
int SV[2020][2020];
int SH[2020][2020];

ll ret;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W;
	FOR(y,H) cin>>A[y];
	A[0][0]=A[H-1][W-1]=A[H-1][0]=A[0][W-1]='#';
	//FOR(y,H) cout<<A[y]<<endl;
	
	FOR(y,H) FOR(x,W) {
		SV[y+1][x+1]=SV[y][x+1]+(A[y][x]=='#');
		SH[y+1][x+1]=SH[y+1][x]+(A[y][x]=='#');
	}
	
	for(y=1;y<H-1;y++) if(SH[y+1][W]-SH[y+1][0]==0) ret++;
	for(x=1;x<W-1;x++) if(SV[H][x+1]-SV[0][x+1]==0) ret++;
	
	for(y=1;y<H-1;y++) for(x=1;x<W-1;x++) {
		if(SH[y+1][x+1]-SH[y+1][0]==0 && SV[y+1][x+1]-SV[0][x+1]==0) ret++;
		if(SH[y+1][x+1]-SH[y+1][0]==0 && SV[H][x+1]-SV[y][x+1]==0) ret++;
		if(SH[y+1][W]-SH[y+1][x]==0 && SV[y+1][x+1]-SV[0][x+1]==0) ret++;
		if(SH[y+1][W]-SH[y+1][x]==0 && SV[H][x+1]-SV[y][x+1]==0) ret++;
	}
	for(y=1;y<H-1;y++) {
		int s[2][2020]={};
		int su[2][2020]={};
		for(x=1;x<W-1;x++) {
			if(SV[y+1][x+1]-SV[0][x+1]==0) s[0][x]=1;
			if(SV[H][x+1]-SV[y][x+1]==0) s[1][x]=1;
			if(A[y][x]=='.') {
				if(A[y][x-1]=='.') {
					if(s[0][x]) ret+=su[1][x-1];
					if(s[0][x]&& x>=2) ret+=su[0][x-2];
					if(s[1][x]) ret+=su[0][x-1];
					if(s[1][x]&& x>=2) ret+=su[1][x-2];
				}
				su[0][x]=su[0][x-1]+s[0][x];
				su[1][x]=su[1][x-1]+s[1][x];
			}
		}
	}
	for(x=1;x<W-1;x++) {
		int s[2][2020]={};
		int su[2][2020]={};
		for(y=1;y<H-1;y++) {
			if(SH[y+1][x+1]-SH[y+1][0]==0) s[0][y]=1;
			if(SH[y+1][W]-SH[y+1][x]==0) s[1][y]=1;
			if(A[y][x]=='.') {
				if(A[y-1][x]=='.') {
					if(s[0][y]) ret+=su[1][y-1];
					if(s[0][y]&& y>=2) ret+=su[0][y-2];
					if(s[1][y]) ret+=su[0][y-1];
					if(s[1][y]&& y>=2) ret+=su[1][y-2];
				}
				su[0][y]=su[0][y-1]+s[0][y];
				su[1][y]=su[1][y-1]+s[1][y];
			}
		}
	}
	
	cout<<ret<<endl;
}

まとめ

yukicoderの自作問で使ったテク(累積和を使った2点間の移動可能判定)が活きた。