AtCoder ARC #203 : E - Tile Grid with One Hole

もっと複雑な解法かと思ったら意外にシンプルだった。
https://atcoder.jp/contests/arc203/tasks/arc203_e

問題

整数H,W,L,N,M,R,Cが与えられる。
H*Wのグリッドのうち、(R,C)を除いた(H*W-1)マスを考える。
これらを、縦1*横Lマスの矩形N個と、縦L*横1マスの矩形M個で覆い切れるか。
可能なら一例を示せ。

解法

極力L*Lの正方形領域に分割する。すると個々の領域は、縦L個または横L個の矩形で埋めることができる。

R,Cを0-originとする。解があるのは以下の2通り。

• H%L=W%L=1、R%L=C%0=1
  • この時、空きマスの上と下を縦長、左と右を横長矩形で埋めることが出来、残りはL*Lの正方形領域で埋めることができる。
• H%L=W%L=L-1、R%L=C%0=L-1
  • この時、空きマスを中心とした(2L-1)*(2L-1)の正方形領域を考える。風車の要領で、縦長・横長の矩形を計4*(L-1)個で、空きマス以外を埋めることができる。
  • この正方形の上下の残った領域のうち、左右幅(L-1)分は縦長矩形で埋める。同様に、左右の領域のうち上下幅(L-1)分は横長矩形で埋める。
  • そうすると、残りはL*Lの正方形領域で埋めることができる。

int T,H,W,L,N,M,R,C;
vector<pair<int,int>> vert,hori;

void prot(int y,int x) {
	int i;
	if(N) {
		N-=L;
		FOR(i,L) hori.push_back({y+i,x});
	}
	else {
		M-=L;
		FOR(i,L) vert.push_back({y,x+i});
	}
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>H>>W>>L>>N>>M>>R>>C;
		R--,C--;
		vert.clear();
		hori.clear();
		if(H%L==1&&W%L==1&&R%L==0&&C%L==0) {
			FOR(y,H/L) vert.push_back({y*L+(y>=R/L),C}),M--;
			FOR(x,W/L) hori.push_back({R,x*L+(x>=C/L)}),N--;
			FOR(y,H/L) FOR(x,W/L) prot(y*L+(y>=R/L),x*L+(x>=C/L));
		}
		else if(H%L==L-1&&W%L==L-1&&R%L==L-1&&C%L==L-1) {
			FOR(i,L-1) {
				vert.push_back({R/L*L,C+1+i});
				vert.push_back({R,C/L*L+i});
				hori.push_back({R/L*L+i,C/L*L});
				hori.push_back({R+1+i,C});
				N-=2;
				M-=2;
			}
			for(y=R/L*L+L;y<R/L*L+2*L-1;y++) for(x=0;x<C-L;x+=L) hori.push_back({y,x}),N--;
			for(y=R/L*L+L;y<R/L*L+2*L-1;y++) for(x=C+L;x<W;x+=L) hori.push_back({y,x}),N--;
			for(y=0;y<R-L;y+=L) for(x=C/L*L+L;x<C/L*L+2*L-1;x++) vert.push_back({y,x}),M--;
			for(y=R+L;y<H;y+=L) for(x=C/L*L+L;x<C/L*L+2*L-1;x++) vert.push_back({y,x}),M--;
			for(y=0;y<R;y+=L) for(x=0;x<C;x+=L) if(y!=R/L*L||x!=C/L*L) prot(y,x);
			for(y=R+L;y<H;y+=L) for(x=0;x<C;x+=L) prot(y,x);
			for(y=0;y<R;y+=L) for(x=C+L;x<W;x+=L) prot(y,x);
			for(y=R+L;y<H;y+=L) for(x=C+L;x<W;x+=L) prot(y,x);
		}
		
		if(N==0&&M==0) {
			cout<<"Yes"<<endl;
			FORR2(r,c,hori) cout<<r+1<<" "<<c+1<<endl;
			FORR2(r,c,vert) cout<<r+1<<" "<<c+1<<endl;
		}
		else {
			cout<<"No"<<endl;
		}
			
		
	}
}

まとめ

他のパターンを埋められないことを、確信をもって判断するのが難しそう。