yukicoder : No.2958 Placing Many L-s

これ理屈で攻めるのと実験で攻めるのどっちがいいんだろう。
https://yukicoder.me/problems/no/2958

問題

H*Wのグリッドを、L字型のテトリミノで埋めることができるか。
出来るなら一例を示せ。
なお、テトリミノは回転や反転させてもよい。

解法

縦横が2マス以上で、全マス数が8の倍数なら可能。

• 縦横の長さがいずれも偶数の場合、全マス数が8の倍数なら縦か横の長さは4の倍数である。テトリミノ2個で4*2の長方形を構成できるので、それを敷き詰めればよい。
• 横の長さが奇数の場合、縦の長さは8の倍数である。テトリミノ6個で8*3の長方形を構成できるので、それを縦に1列並べると、残る横幅は偶数となり、上のパターンに持ち込める。
• 縦の長さが奇数の場合も同様。

int T,H,W;
int A[505][505];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>H>>W;
		int nex=1;
		if(H*W%8||H==1||W==1) {
			cout<<-1<<endl;
			continue;
		}
		
		if(H%4==0&&W%2==0) {
			
			FOR(y,H/4) FOR(x,W/2) {
				A[y*4][x*2]=nex;
				A[y*4][x*2+1]=nex;
				A[y*4+1][x*2]=nex;
				A[y*4+2][x*2]=nex;
				nex++;
				A[y*4+1][x*2+1]=nex;
				A[y*4+2][x*2+1]=nex;
				A[y*4+3][x*2]=nex;
				A[y*4+3][x*2+1]=nex;
				nex++;
			}
		}
		else if(W%4==0&&H%2==0) {
			swap(H,W);
			FOR(y,H/4) FOR(x,W/2) {
				A[y*4][x*2]=nex;
				A[y*4][x*2+1]=nex;
				A[y*4+1][x*2]=nex;
				A[y*4+2][x*2]=nex;
				nex++;
				A[y*4+1][x*2+1]=nex;
				A[y*4+2][x*2+1]=nex;
				A[y*4+3][x*2]=nex;
				A[y*4+3][x*2+1]=nex;
				nex++;
			}
			swap(H,W);
			FOR(y,500) FOR(x,500) if(y<x) swap(A[y][x],A[x][y]);
		}
		else if(H%8==0&&W%2) {
			FOR(y,H/8) {
				A[y*8][0]=A[y*8][1]=A[y*8][2]=A[y*8+1][2]=nex++;
				A[y*8+1][0]=A[y*8+1][1]=A[y*8+2][0]=A[y*8+3][0]=nex++;
				A[y*8+2][1]=A[y*8+2][2]=A[y*8+3][2]=A[y*8+4][2]=nex++;
				A[y*8+3][1]=A[y*8+4][1]=A[y*8+5][1]=A[y*8+5][2]=nex++;
				A[y*8+4][0]=A[y*8+5][0]=A[y*8+6][0]=A[y*8+6][1]=nex++;
				A[y*8+6][2]=A[y*8+7][0]=A[y*8+7][1]=A[y*8+7][2]=nex++;
			}
			FOR(y,H/4) for(x=3;x<W;x+=2) {
				A[y*4][x]=nex;
				A[y*4][x+1]=nex;
				A[y*4+1][x]=nex;
				A[y*4+2][x]=nex;
				nex++;
				A[y*4+1][x+1]=nex;
				A[y*4+2][x+1]=nex;
				A[y*4+3][x]=nex;
				A[y*4+3][x+1]=nex;
				nex++;
			}
			
		}
		else if(W%8==0&&H%2) {
			swap(H,W);
			FOR(y,H/8) {
				A[y*8][0]=A[y*8][1]=A[y*8][2]=A[y*8+1][2]=nex++;
				A[y*8+1][0]=A[y*8+1][1]=A[y*8+2][0]=A[y*8+3][0]=nex++;
				A[y*8+2][1]=A[y*8+2][2]=A[y*8+3][2]=A[y*8+4][2]=nex++;
				A[y*8+3][1]=A[y*8+4][1]=A[y*8+5][1]=A[y*8+5][2]=nex++;
				A[y*8+4][0]=A[y*8+5][0]=A[y*8+6][0]=A[y*8+6][1]=nex++;
				A[y*8+6][2]=A[y*8+7][0]=A[y*8+7][1]=A[y*8+7][2]=nex++;
			}
			FOR(y,H/4) for(x=3;x<W;x+=2) {
				A[y*4][x]=nex;
				A[y*4][x+1]=nex;
				A[y*4+1][x]=nex;
				A[y*4+2][x]=nex;
				nex++;
				A[y*4+1][x+1]=nex;
				A[y*4+2][x+1]=nex;
				A[y*4+3][x]=nex;
				A[y*4+3][x+1]=nex;
				nex++;
			}
			swap(H,W);
			FOR(y,500) FOR(x,500) if(y<x) swap(A[y][x],A[x][y]);
		}
		cout<<H*W/4<<endl;
		FOR(y,H) {
			FOR(x,W) cout<<A[y][x]<<" ";
			cout<<endl;
		}
	}
}

まとめ

シンプルな設定だけど、これ他に出てないのかな。