atcoder.jp
問題
- $H \times W$のマス目と、$N$枚のタイルが与えられるよ
- $i$枚目のタイルは、$ A_i \times B_i $の長方形だよ
- タイルを使って、マス目をピッタリ埋める事ができる？
- 重なったり、空白があったりしちゃだめだよ
- タイルは回転させてもいいよ
成約
- $1 \leq N \leq 7$
- $1 \leq H,W \leq 10$
- $1 \leq A_i, B_i \leq 10$
思考
- 制約が超絶小さい…ので、ゴリ押し力技の全探索
- 一旦計算量を考えてみる
- どのタイルを使う？→bit全探索で$O(2^{N})$
- 使う予定のタイルの、回転どうする？→bit全探索で$O(2^{N})$
- 使う予定のタイルの、順番どうする？→並べ替えで$O(N!)$
- 決めたタイルの使い方、手順を、左上から順に機械的に埋めていく
- もし全タイル丁度埋めきれたら、OK！→判定に$O(H*W)$
- いくら$N,H,W$が小さいとはいえ…これは…
- $2^{N} \times 2^{N} \times N! \times H \times W$
- $=8,257,536,000$…これは、流石に、無理…
- タイルを何枚使うかを、小分けにして考えてみる
- 1枚使うパターン：7通り
- $7\times2^{1}\times 1! \times H \times W = 14HW$
- 2枚使うパターン：7C2=21通り
- $21 \times 2^{2} \times 2! \times H \times W = 168HW$$
- 3枚使うパターン：7C3=35通り
- $35 \times 2^{3}\times 3! \times H \times W = 1,680HW$$
- 4枚使うパターン：7C4=35通り
- $35 \times 2^{4} \times 4! \times H \times W = 13,440HW$
- 5枚使うパターン：7C5=21通り
- $21 \times 2^{5} \times 5! \times H \times W = 80,640HW$
- 6枚使うパターン：7C6=7通り
- $7 \times 2^{6} \times 6! \times H \times W = 322,560HW$
- 7枚使うパターン：7C6=1通り
- $1 \times 2^{7} \times 7! \times H \times W = 645,120HW$
- $H,W$は固定なので、上記パターンに分類される
- 一番重い、7枚使うパターンを、7回回すっていう感覚で、
- $7 \times 645,120 \times10\times 10 = 451,584,000$
- $8,257,536,000$から比べると一気に小さくなった
- 計算量の見積もり、とても、難しい…
コード
import itertools
N, H, W = map(int, input().split())
tiles = []
for i in range(N):
A, B = map(int, input().split())
tiles.append([A, B])
master = [[1] * W for _ in range(H)]
def calc(tiles):
base = [[0] * W for _ in range(H)]
cur = 0
for i in range(H):
for j in range(W):
if len(tiles) == cur: break
if base[i][j] != 0: continue
tile_x, tile_y = tiles[cur]
if i + tile_x > H or j + tile_y > W: return False
for x in range(i, i + tile_x):
for y in range(j, j + tile_y):
if base[x][y] != 0: return False
base[x][y] = 1
cur += 1
if base == master:
return True
return False
for saiyou in range(1, 1 << N):
saiyou_tiles = []
area_sum = 0
for i in range(N):
if saiyou >> i & 1:
saiyou_tiles.append(tiles[i])
area_sum += tiles[i][0] * tiles[i][1]
tile_cnt = len(saiyou_tiles)
for omoteura in range(1 << tile_cnt):
omoteura_tiles = []
for i in range(tile_cnt):
if omoteura >> i & 1:
omoteura_tiles.append(saiyou_tiles[i])
else:
omoteura_tiles.append([saiyou_tiles[i][1], saiyou_tiles[i][0]])
for junban in itertools.permutations(omoteura_tiles):
if calc(junban):
print('Yes')
exit()
print('No')
