ちょっと考えすぎた。
https://agc021.contest.atcoder.jp/tasks/agc021_c
問題
N*Mのグリッドに、縦1×横2マス分のタイルA枚と縦2×横1マス分のタイルB枚をマス目に沿ってはめ込むことができるか。
できるならその例を示せ。
なおタイルの回転は許可されない。
解法
2*2の領域があれば、前者のタイル2枚または後者のタイル2枚を埋めることができる。
そこで、まず高さNが奇数なら最下段を横長タイルで埋め、幅Mが奇数なら最右列を縦タイルで埋めてみよう。
後は高さも幅も偶数なので2*2の領域で埋め尽くせるため、両タイルを埋めていくことができる。
これで全タイルが埋め込めればそれでよし。
ただし1点例外ケースがある。
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には気が付いたものの、偶数ケースを無駄に考えすぎて時間切れ。