AtCoder Beginner Contest 345, D : Tiling

問題文

　https://atcoder.jp/contests/abc345/tasks/abc345_d

問題概要

　$1 \times 1$ のセルからなる $h \times w$ のグリッド状の盤面と $n$ 枚のタイルがあり，タイル $i$ は $A_i \times B_i$ の長方形状である．
　各タイルについて，グリッドに沿い，かつ盤面からはみ出さない範囲で自由に位置と向きを決めてグリッドに配位することができる（配置しなくてもよい）．
　グリッドのすべてのセルがちょうど $1$ 枚のタイルに被覆されている状態にできるか？

制約

• $1 \leq n \leq 7$
• $1 \leq h, w \leq 10$
• $1 \leq A_i, B_i \leq 10$

解法

　あまり賢い方法が思いつかず，また制約も小さいので配置をすべて試すことをベースに考えていきます．とはいえあまりにエレファントなことをするのはこわいので，明らかな無駄は省いていきます．
　タイルを（$i$ の昇順とは限らない順序で）一枚ずつ順に置いていくことを考えます．この過程で（$0$ 枚以上の）何枚かのタイルを配置し終えたとき，$2$ 枚以上のタイルに被覆されたセルが無く，目標状態にも到達していないのならば，タイルに全く被覆されていないセル（以降，空セルと呼ぶ）が $1$ つ以上存在します*1．そのようなセルの内，最も左上*2にあるものの座標を $( \mathit{ ty }, \mathit{ tx } )$ とします．このとき，セル $( \mathit{ ty }, \mathit{ tx } )$ の上も左も空セルではないので，ここはいずれかのタイルの左上となります．ということで次に置く位置が確定したので残りの選択肢は，

• 未使用タイルの内，どのタイルを選ぶか
• どの向きで置くか

ですが，後者は選ぶタイルを $i$ として $A_i \times B_i$ の長方形として扱うか $B_i \times A_i$ の長方形として扱うかの $2$ 通りです．（途中で invalid になったら弾くとして，）タイルの順序は $O( n! )$ 通りあって，そのそれぞれについて各タイルを置く向きの二択が $O( n )$ 個あるので，出現する状態数は $O( n! 2^n )$ 通りです．
　そのそれぞれの状態について，

• $O( hw )$ 時間で $( \mathit{ ty }, \mathit{ tx } )$ を特定
• $\Theta( n )$ 時間で次に置くタイルを選ぶ
• $O( hw )$ 時間で各セルの被覆数を更新する

などのことをします*3．従って，全体では $O( n! 2^n ( n + wh ) )$ 時間となります．制約を考えるとこれは十分高速に動作します．

コード

bool filled( const VVI &board )
{
	return all_of( ALL( board ), []( const VI &row )
			{ return all_of( ALL( row ), []( const int a ){ return a == 1; } ); } );
}

PII first_empty( const VVI &board )
{
	const int H = SZ( board ), W = SZ( board[0] );

	REP( i, H )
	{
		REP( j, W )
		{
			if ( board[i][j] == 0 )
			{
				return { i, j };
			}
		}
	}

	return { 0, 0 };
}

void dfs( const VI &A, const VI &B, VVI board, VI used )
{
	const int N = SZ( A );
	const int H = SZ( board ), W = SZ( board[0] );

	if ( filled( board ) )
	{
		cout << "Yes" << endl;
		exit( 0 );
	}

	const auto [ ty, tx ] = first_empty( board );
	const auto put = [&]( const int i, const int a, const int b )
	{
		if ( ty + a <= H && tx + b <= W )
		{
			auto nboard = board;
			bool ok = true;
			REP( y, ty, ty + a )
			{
				REP( x, tx, tx + b )
				{
					ok &= ++nboard[y][x] == 1;
				}
			}

			auto nused = used;
			nused[i] = 1;

			if ( ok )
			{
				dfs( A, B, nboard, nused );
			}
		}
	};

	REP( i, N )
	{
		if ( !used[i] )
		{
			put( i, A[i], B[i] );
			put( i, B[i], A[i] );
		}
	}

	return;
}

int main()
{
	IN( int, N, H, W );
	VI A( N ), B( N );
	REP( i, N )
	{
		cin >> A[i] >> B[i];
	}

	VVI board( H, VI( W ) );
	VI used( N );
	dfs( A, B, board, used );
	cout << "No" << endl;

	return 0;
}

*1:各セルを被覆するタイルの枚数は $0$ または $1$ で，すべて $1$ ならば目標状態なので，空セルが存在する．

*2:座標を順序対と見たときの時辞書式順序で最小のもの

*3:他にも細かいことをしますが，計算量としては定数倍の中に消えます．