AtCoder AGC #021 : C - Tiling

ちょっと考えすぎた。
https://agc021.contest.atcoder.jp/tasks/agc021_c

問題

N*Mのグリッドに、縦1×横2マス分のタイルA枚と縦2×横1マス分のタイルB枚をマス目に沿ってはめ込むことができるか。
できるならその例を示せ。
なおタイルの回転は許可されない。

解法

2*2の領域があれば、前者のタイル2枚または後者のタイル2枚を埋めることができる。
そこで、まず高さNが奇数なら最下段を横長タイルで埋め、幅Mが奇数なら最右列を縦タイルで埋めてみよう。
後は高さも幅も偶数なので2*2の領域で埋め尽くせるため、両タイルを埋めていくことができる。
これで全タイルが埋め込めればそれでよし。

ただし１点例外ケースがある。
3*3の領域があれば、外周部に両タイルを2枚ずつ埋めることができる。
よって、上記パターンでうまくいかない場合、右下に3*3の領域を1つおいて、あとは上記パターンと同様になるケースを試してみよう。
なお実際これが効果があるのはN,Mが奇数の場合のみである。

int H,W,A,B;
int OH,OW,OA,OB;

string S[1010];

void output() {
	int y;
	cout<<"YES"<<endl;
	FOR(y,OH) cout<<S[y]<<endl;
	exit(0);
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W>>A>>B;
	if(H*W<2*(A+B)) return _P("NO\n");
	OH=H,OW=W,OA=A,OB=B;
	
	FOR(y,H) S[y]=string(W,'.');
	if(H%2==1) {
		for(x=0;x<W-1&&A;x+=2) S[H-1][x]='<', S[H-1][x+1]='>', A--;
		H--;
	}
	if(W%2==1) {
		for(y=0;y<H-1&&B;y+=2) S[y][W-1]='^', S[y+1][W-1]='v', B--;
		W--;
	}
	
	for(y=0;y<H;y+=2) {
		for(x=0;x<W;x+=2) {
			if(A) {
				S[y][x]='<', S[y][x+1]='>', A--;
				if(A) S[y+1][x]='<', S[y+1][x+1]='>', A--;
			}
			else if(B) {
				S[y][x]='^', S[y+1][x]='v', B--;
				if(B) S[y][x+1]='^', S[y+1][x+1]='v', B--;
			}
		}
	}
	if(A==0 && B==0) output();
	
	H=OH,W=OW,A=OA,B=OB;
	if(H%2 && W%2 && H>=3 && W>=3 && A>=2 && B>=2) {
		A-=2;
		B-=2;
		FOR(y,H) S[y]=string(W,'.');
		S[H-3][W-3]=S[H-1][W-2]='<';
		S[H-3][W-2]=S[H-1][W-1]='>';
		S[H-2][W-3]=S[H-3][W-1]='^';
		S[H-1][W-3]=S[H-2][W-1]='v';
		for(y=0;y<H-3&&B;y+=2) S[y][W-1]='^',S[y+1][W-1]='v',B--;
		for(x=0;x<W-3&&A;x+=2) S[H-1][x]='<',S[H-1][x+1]='>',A--;
		for(y=0;y<H-1;y+=2) {
			for(x=0;x<W-1;x+=2) {
				if(S[y][x]!='.') continue;
				if(A) {
					S[y][x]='<', S[y][x+1]='>', A--;
					if(A) S[y+1][x]='<', S[y+1][x+1]='>', A--;
				}
				else if(B) {
					S[y][x]='^', S[y+1][x]='v', B--;
					if(B) S[y][x+1]='^', S[y+1][x+1]='v', B--;
				}
			}
		}
		if(A==0 && B==0) output();
	}
	
	
	cout<<"NO"<<endl;
	
}

まとめ

3*3には気が付いたものの、偶数ケースを無駄に考えすぎて時間切れ。