ABC解説

ABC345 D問題の解説（Python）

はじめに

この記事では、ABC345のD問題を解説していきます。

ABC（AtCoder Beginner Contest）とは、AtCoderが開催している、競技プログラミングコンテストです。

ABC345　D-Tiling

問題

問題

H行W列のマス目とN枚の長方形タイルがあります。i枚目のタイルは、\(A_i × B_i\) の長方形です。これらの長方形タイルで全てのマス目を埋めることができるかを判定する問題です。使用しないタイルがあってもよく、タイル同士は重なってはいけません。

制約

  • \(1 \leqq N \leqq 7\)
  • \(1 \leqq H, W \leqq 10\)
  • \(1 \leqq A_i, B_i \leqq 10\)

思考の筋道

Nは7以下、HとWは10以下と値が非常に小さいです。そのため全ケース、地道に配置していく方法で十分間に合います。しかしその実装が大変です。実装力が問われますね。

以下の流れで考えます。

  1. 使うタイルの組を決定する
    使うタイルの組を決定します。なお、選んだタイルの面積の合計が、マスの面積の合計HWと等しくなければ、その時点でアウトなので、次の組にいきましょう。
  2. タイルを使う順番を決定する
    組の中で、タイルを使う順番を決定します。なぜ順番を決める必要があるかというと、その順番に基づいて、左上から詰めるようにタイルを配置していくためです。
  3. 左上のマスから調べ、どこが空きマスか調べる
    はじめに見つけた空きマスを、これから置くタイルの左上の角として考えます。
  4. タイルを配置する
    タイルを配置する際、そのタイルが盤からはみ出してしまったり、別のタイルと重なってしまう場合は、その順番では配置できないということです。諦めて次のケースにいきましょう。タイルが配置できた場合は、それが最後のタイルであれば配置完了です。まだ次のタイルがあれば、3のステップに戻ります（再帰処理）。

配置完了するケースが 1 つでもあればYesを出力し、1つもなければNoを出力しましょう。

下のコードはこの流れを実装したものですが、もっと上手く書けるかもしれません。

コード

from itertools import combinations, permutations

N, H, W = map(int, input().split())
blocks = [list(map(int, input().split())) for _ in range(N)]

def can_place(idx, muki):
    if idx == len(chosen_order):
        return True

    h, w = blocks[chosen_order[idx]]
    if muki:
        h, w = w, h
    start_i, start_j = 0, 0
    flg = False
    for i in range(H):
        for j in range(W):
            if m[i][j] == 0:
                start_i, start_j = i, j
                flg = True
                break
        if flg:
            break
    for di in range(h):
        for dj in range(w):
            if start_i + di >= H or start_j + dj >= W or m[start_i + di][start_j + dj] == 1:
                return False
    for di in range(h):
        for dj in range(w):
            m[start_i + di][start_j + dj] = 1
    idx += 1
    for muki in range(2):
        if can_place(idx, muki):
            return True

for i in range(1, N + 1):
    for chosen_blocks in combinations(range(N), i):
        if sum([blocks[x][0] * blocks[x][1] for x in chosen_blocks]) != H * W:
            continue
        for chosen_order in permutations(chosen_blocks):
            for muki in range(2):
                m = [[0] * W for _ in range(H)]
                idx = 0

                if can_place(idx, muki):
                    print("Yes")
                    exit()
print("No")

以上、ABC345のD問題の解説でした！

では、またね。

リンク

ABC345
情報科学の部屋へ