D - Tiling Editorial by mechanicalpenciI
マス目の上から \(i\) 行目かつ \(j\) 列目のマスを \((i,j)\) とよび、 また \(i\) 枚目のタイルを単にタイル \(i\) と呼びます。
最初に、問題文の条件から回転は \(90\) 度単位でしか許されず、各タイルを置くときの向きは 正方形型 \((A_i=B_i)\) 型のタイルで \(1\) 通り、そうでないときに \(2\) 通り( \(A_i\times B_i\) または \(B_i\times A_i\)) しかあり得ないことに注意します。
次に、タイルを \(1\) 枚ずつ置いていく方法を全探索する方法について考えます。 問題文中の条件をみたすタイルの置き方が存在したとして、それが条件をみたすかどうかは使用したタイルを置いた順番によりません。 そこで、次のような順番で置いていくという条件を付加しても答え (Yes/No) は変わりません。
マス目の番号の辞書順、すなわち \((1,1)\), \((1,2)\), \(\ldots\), \((1,W)\), \((2,1)\), \((2,2)\), \(\ldots\), \((N,N-1)\), \((N,N)\) の順でマスを見た時、まだタイルで覆われていないマスのうち最初に出てきたものをマス \(X\) とする。(全てのマスがタイルで覆われていたらそこで直ちに操作を終了する。)その後、タイルとその向きを選び、マス \(X\) を覆うことができるように(かつマス目からはみ出したり他のタイルと重なることがないように)置く。
このとき、それぞれの時のマス \(X\) の \(1\) つ左と \(1\) つ上はマスが存在しない(マス目の外側)か、タイルの置かれたマスとなっています。よって、タイルの置き方はマス \(X\) (の左上角)にそのタイルの左上角を重ねるような置き方しかできません。 タイルの向きが高々 \(2\) 通りしかないことを合わせると、 このような順で置いた時、それぞれのタイミングでタイルと向きを選ぶ方法は高々(まだ使用されていないタイルの枚数)\(\times 2\) 通りしかありません。
よって、タイルを使用する順番とそれぞれのタイルを置く向きが決まっていれば、タイルの置き方はできるならば一意(途中でマス目からはみ出したり他のタイルと重なってしまったら失敗、そうでなければ置き方は一意)に定まります。さらに、もし問題文中の条件をみたす置き方が存在したとすると、必ずそれに対応する順番が存在します。なぜなら、条件をみたすようなタイルの配置を考え、そのマス目をマス目の番号の辞書順で見たときにタイルが登場する順番とそれらの向きを指定すれば、上記の置き方でかならず再現できるからです。
よって、タイルを使用する順番とそれぞれのタイルを置く向きの組み合わせについて全探索を行なったとすると、条件をみたす置き方が存在するならばかならず発見することができます。
このとき、マス \(X\) を探すのに必要な計算回数は、それぞれの選び方と向きの組み合わせについて(その組み合わせについての最大 \(N\) 回の探索について)合計 \(HW\) 回であることから、全体での計算回数は \(N!\times 2^N\times HW\) 回であり、今回の制約下で 高々 \(6.5\times 10^7\) 回未満となるため、十分高速です。マス \(X\) の位置はそれまでに使用されたタイルの順番と向きにしか依存しないことから、再帰的に計算を行うとより早く計算を行うことができます。また、ある置き方について途中でマス目からはみ出したり他のタイルと重なったりした場合はそれ以降の置き方を調べる必要はないため、枝刈りを行うことができます。
最後に注意点として、使用しないタイルが存在する可能性があるため、ある時点でマス \(X\) を探した際にすべてのマスが覆われていたら答えは Yes
となることに注意してください。
よって、この問題を解くことができました。
なお、この問題にはいくつかの解法が存在します。特に、\(N,H,W\) が小さいため、何かしらの方法で全探索する方針が有効です。計算回数を見積もった上で時間制限に間に合うと考えられるものであれば、いずれも問題ありません。
c++ による実装例:
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < n; ++i)
#define MAX_N 7
#define MAX_H 10
#define MAX_W 10
int n,h,w;
int a[MAX_N];
int b[MAX_N];
int c[MAX_H][MAX_W];
bool ans;
void solve(int unused,int curi,int curj){
bool can;
while(c[curi][curj]>=0){
curj++;
if(curj>=w){curi++;curj=0;}
if(curi>=h)break;
}
if(curi>=h){ans=true;return;}
rep(i,n){
if(unused&(1<<i)){
can=true;
rep(ii,a[i]){
rep(jj,b[i]){
if(((curi+ii)<h)&&((curj+jj)<w)){
if(c[curi+ii][curj+jj]<0)c[curi+ii][curj+jj]=i;
else {can=false;}
}
else {can=false;}
}
}
if(can)solve(unused^(1<<i),curi,curj);
rep(ii,a[i]){
rep(jj,b[i]){
if(((curi+ii)<h)&&((curj+jj)<w)){
if(c[curi+ii][curj+jj]==i)c[curi+ii][curj+jj]=-1;
}
}
}
if(a[i]!=b[i]){
can=true;
rep(ii,b[i]){
rep(jj,a[i]){
if(((curi+ii)<h)&&((curj+jj)<w)){
if(c[curi+ii][curj+jj]<0)c[curi+ii][curj+jj]=i;
else can=false;
}
else can=false;
}
}
if(can)solve(unused^(1<<i),curi,curj);
rep(ii,b[i]){
rep(jj,a[i]){
if(((curi+ii)<h)&&((curj+jj)<w)){
if(c[curi+ii][curj+jj]==i)c[curi+ii][curj+jj]=-1;
}
}
}
}
}
}
return;
}
int main(void){
cin>>n>>h>>w;
rep(i,n)cin>>a[i]>>b[i];
rep(i,h)rep(j,w)c[i][j]=-1;
ans=false;
solve((1<<n)-1,0,0);
if(ans)cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
posted:
last update: