AtCoder Beginner Contest 196 D Hanjo

この記事について

• AtCoder Beginner Contest 196 D Hanjo について、以下の人向けの解法を紹介
  • DFS を死んでも書きたくない人
• 文責: kys

問題

• AtCoder Beginner Contest 196 D Hanjo
  • 縦 $H$ メートル、横 $W$ メートルの部屋に以下を敷き詰める場合の数を求める問題
    • $2$ メートル $\times~1$ メートルの互いに区別できない $A$ 枚の畳（縦長にも横長にも使える）
      • 以降、長方形の畳と呼ぶ
    • $1$ メートル $\times~1$ メートルの互いに区別できない $B$ 枚の畳
      • 以降、正方形の畳と呼ぶ
  • 部屋全体の回転や反転は区別
  • 制約
    • $1 \leq H, W$
    • $HW \leq 16$
    • $0 \leq A, B$
    • $2 A + B = HW$

解法

気持ち

• 以下を全探索
  1. $H \times W$ 枚の正方形の畳で部屋を埋めたことにする
  2. 部屋の外周に包含されない畳の縁（ヘリ）を $A$ 回破壊する
  3. できあがった部屋が正方形の畳と長方形の畳で構築可能ならカウンタをインクリメント

やり方

1. 各ノードが部屋の 1 マスに対応した Union−Find 木を用意する
2. 破壊したい畳の縁を構成する 2 つのマスに対して、対応する Union−Find 木のノードを unite する
3. 出来上がった Union−Find 木に、サイズ 3 以上の木が含まれていないことを確認する
   • ここで、高速化のために、unite した直後にその木のサイズを確認し、3 以上であれば即時 break

Python3 による実装

from itertools import combinations

class UnionFindTree:
    def __init__(self, initial_size:int) -> None:
        self.n_nodes = initial_size
        self.parents = [i for i in range(initial_size)]
        self.ranks = [0 for i in range(initial_size)]
        self.size = [1 for i in range(initial_size)]
    def root(self, n:int) -> int:
        if self.parents[n] == n:
            return n
        else:
            self.parents[n] = self.root(self.parents[n])
            return self.parents[n]
    def same(self, n:int, m:int) -> bool:
        return (self.root(n) == self.root(m))
    def unite(self, n:int, m:int) -> None:
        if self.same(n, m):
            return
        n, m = self.root(n), self.root(m)
        if self.ranks[n] < self.ranks[m]:
            self.parents[n] = m
            self.size[m] += self.size[n]
        else:
            self.parents[m] = n
            self.size[n] += self.size[m]
            if self.ranks[n] == self.ranks[m]:
                self.ranks[n] += 1
    def get_roots(self) -> set:
        return set([self.root(x) for x in range(self.n_nodes)])
    def count_roots(self) -> int:
        return len(self.get_roots())
    def get_tree_size(self, n:int) -> int:
        return self.size[self.root(n)]

H, W, A, B = list(map(int, input().split()))
if A == 0:
    print(1)
    exit(0)

ans = 0
cand = [] # 破壊可能な縁の候補を、その縁を共有する 2 マスのタプルによって表現
for i in range(H):
    for j in range(W - 1):
        cand.append((W * i + j, W * i + j + 1)) # 横に並んだ 2 マス
for i in range(H - 1):
    for j in range(W):
        cand.append((W * i + j, W * i + j + W)) # 縦に並んだ 2 マス

for pairs in combinations(cand, A):
    uft = UnionFindTree(H * W)
    ok = True
    for i, j in pairs:
        uft.unite(i, j)
        if uft.get_tree_size(i) > 2:
            ok = False
            break
    if ok:
        ans += 1
print(ans)

考察

• よく考えたら、以下で良かった（この記事を書きながら気がついた）
  1. サイズ $H \times W$ ブール配列を用意する
  2. 縁の破壊時にその縁を共有する 2 マスを True から False に書き換える。もし、もともと False だったら即時 break
• $O \left({}_{(H - 1)W + H(W - 1)} \mathrm{C}_A \times A \right)$ は、ユニファでごちゃごちゃやっても間に合う
  • このランダウの記法（？）あってるんか？
• 提出

まとめ

• いかがでしたか？ AtCoder Beginner Contest 196 D Hanjo について、DFS を死んでも書きたくない人向けの解法をご紹介させていただきました！