まず、先にシート \(C\) から切り出す範囲を決めておいてもシート \(X\) を作る事ができるかは変わりません。

そこで、まずシート \(C\) のマス目に座標をつけます。 切り出す \(H_X\times W_X\) の領域の左上のマスを \((0,0)\) とし、そこから \(a\) 行下かつ \(b\) 列右のマスを \((a,b)\) で表します。ただし、\(a,b\) が負の時はそれぞれ、 \(\lvert a\rvert\) 行上, \(\lvert b\rvert\) 列左を表すものとします。すなわち、\(0\leq i\leq a-1\), \(0\leq j\leq b-1\) をみたす \((i,j)\) からなるマス目を切り出します。これを領域 \(D\) とします。

解法 \(1\)

さて、シート \(A\) を貼る領域について考えます。 シート \(A\) は黒マスを含み、領域 \(D\) はシート \(A\) 上の黒マスを全て含む事からシート \(A\) を貼る領域と領域 \(D\) は \(1\) マス以上共有している必要があります。よって、シート \(A\) の左上のマスを貼り付ける先の(シート \(C\) 上の)マスとしてあり得るのは、 \((i,j)\) \((-H_A+1\leq i\leq H_X-1, -W_A+1\leq i\leq W_X-1)\) となります。 同様に、シート \(B\) の左上のマスを貼り付ける先の(シート \(C\) 上の)マスとしてあり得るのは、 \((i,j)\) \((-H_B+1\leq i\leq H_X-1, -W_B+1\leq i\leq W_X-1)\) となります。

それぞれのシートについて貼る位置を決めた時、問題文中の \(2\) つの条件がみたされているかは、\(H_A\times W_A\), \(H_B\times W_B\) のマス目においてすべての黒マスの貼った先が領域 \(D\) に含まれているか、 \(H_X\times W_X\)のマス目が目標としているシート \(X\) と一致しているかを確認するだけで良いです。

シート\(A,B\) を貼る場所の候補はそれぞれ \(19\times 19\) 通り、 条件をみたしているか判定するために調べる場所はのべ \(3\times(10\times 10)\) マスである事から、全体で \((19\times 19)^2\times 300\) 回となり、十分時間内に間に合います。 よって、この問題を解く事ができました。

なお、実装においては、細かい実装方針にもよりますが、

• 配列のindexは多くの言語において非負であることが好ましいため、切り出す領域の左上のマスを \((10,10)\) とする。
• マス目の大きさに依存しない形にするため、シート \(A,B,X\) に必要ならば透明なマスのみからなる行, 列を加えてつねに \(10\times 10\) のマス目とみなす。

といった工夫をすると実装が楽になるかもしれません。

解法 \(2\)

シート \(A,B,X\) の黒マスのうち、それぞれのシートの黒マスの中で最も上の行に属し、その中で最も左にあるマスを各シートの良い黒マスとすると、条件をみたすように切り出せた時、シート \(X\) の良い黒マスに対応するマスには シート \(A\) または \(B\) の良い黒マスが貼り付けられていることになります。良い黒マスを一致させるために貼らなければならない場所は一意に定まるため、シート \(A\) の黒マスと一致する時、シート \(B\) の黒マスと一致する時のそれぞれについて、もう一方のシートを貼る場所の候補をすべて試せば良いです。(下の実装例では実装の都合上右下のマスを良いマスとしています。)

この時、比較回数は全体で \(2\times (19\times 19)\times 300\) 回となり、より高速です。

c++ による実装例 \(1\) (解法 \(1\)):

#include <bits/stdc++.h>

using namespace std;
#define rep(i, n) for(int i = 0; i < n; ++i)

int main(void){
	string a[3][10];
	char tmp[10][11];
	int h[3],w[3];
	bool flag;
	for(int k=0;k<3;k++){
		cin>>h[k]>>w[k];
		for(int i=0;i<h[k];i++)cin>>a[k][i];
	}

	for(int dh0=-h[0]+1;dh0<h[2];dh0++){
		for(int dw0=-w[0]+1;dw0<w[2];dw0++){
			for(int dh1=-h[1]+1;dh1<h[2];dh1++){
				for(int dw1=-w[1]+1;dw1<w[2];dw1++){
					for(int i=0;i<h[2];i++)for(int j=0;j<w[2];j++)tmp[i][j]='.';
					flag=true;

					for(int i=0;i<h[0];i++){
						for(int j=0;j<w[0];j++){
							if(a[0][i][j]=='#'){
								if(i+dh0<0)flag=false;
								if(i+dh0>=h[2])flag=false;
								if(j+dw0<0)flag=false;
								if(j+dw0>=w[2])flag=false;
								if(flag)tmp[i+dh0][j+dw0]='#';
							}
						}
					}
					for(int i=0;i<h[1];i++){
						for(int j=0;j<w[1];j++){
							if(a[1][i][j]=='#'){
								if(i+dh1<0)flag=false;
								if(i+dh1>=h[2])flag=false;
								if(j+dw1<0)flag=false;
								if(j+dw1>=w[2])flag=false;
								if(flag)tmp[i+dh1][j+dw1]='#';
							}
						}
					}
					for(int i=0;i<h[2];i++){
						for(int j=0;j<w[2];j++){
							if(a[2][i][j]!=tmp[i][j])flag=false;
						}
					}

					if(flag){
						cout<<"Yes"<<endl;
						return 0;
					}

				}
			}
		}
	}

    cout<<"No"<<endl;
	return 0;
}

c++ による実装例 \(2\) (解法 \(1\)):

#include <bits/stdc++.h>

using namespace std;
#define rep(i, n) for(int i = 0; i < n; ++i)

int main(void){
	string a[3][10];
	char tmp[30][31];
	int h[3],w[3];
	bool flag;
	for(int k=0;k<3;k++){
		cin>>h[k]>>w[k];
		for(int i=0;i<h[k];i++)cin>>a[k][i];
	}

	for(int dh0=1;dh0<20;dh0++){
		for(int dw0=1;dw0<20;dw0++){
			for(int dh1=1;dh1<20;dh1++){
				for(int dw1=1;dw1<20;dw1++){
					for(int i=0;i<30;i++)for(int j=0;j<30;j++)tmp[i][j]='.';
					for(int i=0;i<h[0];i++)for(int j=0;j<w[0];j++)if(a[0][i][j]=='#')tmp[i+dh0][j+dw0]='#';
					for(int i=0;i<h[1];i++)for(int j=0;j<w[1];j++)if(a[1][i][j]=='#')tmp[i+dh1][j+dw1]='#';	

					flag=true;
					for(int i=0;i<30;i++){
						for(int j=0;j<30;j++){
							if((0<=(i-10))&&((i-10)<h[2])&&(0<=(j-10))&&((j-10)<w[2])){
								if(tmp[i][j]!=a[2][i-10][j-10])flag=false;
							}
							else{
								if(tmp[i][j]!='.')flag=false;
							}
						}
					}			

					if(flag){
						cout<<"Yes"<<endl;
						return 0;
					}

				}
			}
		}
	}

    cout<<"No"<<endl;
	return 0;
}

c++ による実装例 \(3\) (解法 \(2\)):

#include <bits/stdc++.h>

using namespace std;
#define rep(i, n) for(int i = 0; i < n; ++i)

int main(void){
	string a[3][10];
	char tmp[30][31];
	int h[3],w[3];
	int dh0,dw0,dh1,dw1;
	int gh[3],gw[3];
	bool flag;
	for(int k=0;k<3;k++){
		cin>>h[k]>>w[k];
		for(int i=0;i<h[k];i++){
			cin>>a[k][i];
			for(int j=0;j<w[k];j++)if(a[k][i][j]=='#')gh[k]=i,gw[k]=j;
		}
	}

	dh0=gh[2]-gh[0]+10,dw0=gw[2]-gw[0]+10;
	for(int dh1=1;dh1<20;dh1++){
		for(int dw1=1;dw1<20;dw1++){
			for(int i=0;i<30;i++)for(int j=0;j<30;j++)tmp[i][j]='.';
			for(int i=0;i<h[0];i++)for(int j=0;j<w[0];j++)if(a[0][i][j]=='#')tmp[i+dh0][j+dw0]='#';
			for(int i=0;i<h[1];i++)for(int j=0;j<w[1];j++)if(a[1][i][j]=='#')tmp[i+dh1][j+dw1]='#';	

			flag=true;
			for(int i=0;i<30;i++){
				for(int j=0;j<30;j++){
					if((0<=(i-10))&&((i-10)<h[2])&&(0<=(j-10))&&((j-10)<w[2])){
						if(tmp[i][j]!=a[2][i-10][j-10])flag=false;
					}
					else{
						if(tmp[i][j]!='.')flag=false;
					}
				}
			}		

			if(flag){
				cout<<"Yes"<<endl;
				return 0;
			}

		}
	}

	dh1=gh[2]-gh[1]+10,dw1=gw[2]-gw[1]+10;
	for(int dh0=1;dh0<20;dh0++){
		for(int dw0=1;dw0<20;dw0++){
			for(int i=0;i<30;i++)for(int j=0;j<30;j++)tmp[i][j]='.';
			for(int i=0;i<h[0];i++)for(int j=0;j<w[0];j++)if(a[0][i][j]=='#')tmp[i+dh0][j+dw0]='#';
			for(int i=0;i<h[1];i++)for(int j=0;j<w[1];j++)if(a[1][i][j]=='#')tmp[i+dh1][j+dw1]='#';	

			flag=true;
			for(int i=0;i<30;i++){
				for(int j=0;j<30;j++){
					if((0<=(i-10))&&((i-10)<h[2])&&(0<=(j-10))&&((j-10)<w[2])){
						if(tmp[i][j]!=a[2][i-10][j-10])flag=false;
					}
					else{
						if(tmp[i][j]!='.')flag=false;
					}
				}
			}		

			if(flag){
				cout<<"Yes"<<endl;
				return 0;
			}

		}
	}


    cout<<"No"<<endl;
	return 0;
}