Day 097-Q1 — 輪郭線DP（Broken Profile DP・グリッドのドミノ完全被覆数え上げ）

2026-07-20 赤色 Master / Phase 8+ ★★★★★★★★★ Broken Profile DP

問題

$H \times W$ のグリッドが与えられる。各マスは .（空きマス）または #（壁・使用不可）のいずれかである。

空きマスをすべて $1\times 2$ または $2\times 1$ のドミノで、重複・はみ出しなく敷き詰める方法の総数を $998244353$ で割った余りを求めよ。壁のマスは覆う必要がない（盤面から除外されているとみなす）。

入力形式

H W
row_1
row_2
:
row_H

制約

$1 \le H, W \le 12$
各行は . と # のみからなる長さ $W$ の文字列

入出力例

入力例1

2 2
..
..

出力例1

2

2×2 の空きマス全体を、横ドミノ2枚で敷くパターンと、縦ドミノ2枚で敷くパターンの2通り。

入力例2

2 3
..#
#..

出力例2

1

壁を避けると空きマスは4マス。(0,0)-(0,1) と (1,1)-(1,2) を横ドミノにする1通りのみが有効。

概念図

輪郭線（broken profile）のイメージ：行 i を処理中 埋済 埋済 未定 未定 縦↓ 縦↓ ? ? 行 i-1（上） mask = 1100 : 列0,1が縦ドミノで下（行i）に強制的に埋まる 行 i を左から走査: rec(j, mask_out) で横/縦ドミノを再帰的に決定 最終行の後 mask=0 のときのみ完全被覆として採用

ヒント（段階的開示）

ヒント1: 方向性
すべての敷き詰め方を単純に列挙すると指数的に爆発する。マスを左上から1マスずつ順番に処理していくとき、「まだ確定していないが、直前に処理した行から縦ドミノで下に伸びてくることが決まっているマス」の集合だけを覚えておけば十分ではないか、と考えよ。
ヒント2: アプローチ
輪郭線DP（broken profile DP）: 行ごとに処理する。dp[mask] を「これまでの行を全て正しく埋め終えていて、現在処理しようとしている行のうち、上の行から縦ドミノで強制的に埋まっている列の集合が mask である場合の敷き詰め方の数」と定義する。1行分の遷移は、その行の列を左から順に走査する再帰関数で全パターンを列挙し、次の行に引き継ぐビットマスクを作る。
ヒント3: 誘導（コード骨格） 
def make_transitions(row, mask_in, W, has_next_row):
    results = []
    def rec(j, mask_out):
        if j == W:
            results.append(mask_out)
            return
        if row[j] == '#':
            if (mask_in >> j) & 1:
                return  # 壁に縦ドミノが伸びてきたら矛盾
            rec(j + 1, mask_out)
            return
        if (mask_in >> j) & 1:
            rec(j + 1, mask_out)
            return
        if has_next_row:
            rec(j + 1, mask_out | (1 << j))
        if j + 1 < W and row[j + 1] != '#' and not ((mask_in >> (j + 1)) & 1):
            rec(j + 2, mask_out)
    rec(0, 0)
    return results

最後の行を処理し終えたあと、mask == 0（下にはみ出すドミノがない）のときの dp 値だけが正しい完全被覆の数になる。

模範解答 (Python)

import sys


def solve():
    data = sys.stdin.read().split('\n')
    H, W = map(int, data[0].split())
    grid = [data[i + 1] for i in range(H)]
    MOD = 998244353

    dp = {0: 1}
    for i in range(H):
        row = grid[i]
        has_next_row = (i + 1 < H)
        ndp = {}
        for mask_in, ways in dp.items():
            def rec(j, mask_out):
                if j == W:
                    ndp[mask_out] = (ndp.get(mask_out, 0) + ways) % MOD
                    return
                if row[j] == '#':
                    if (mask_in >> j) & 1:
                        return
                    rec(j + 1, mask_out)
                    return
                if (mask_in >> j) & 1:
                    rec(j + 1, mask_out)
                    return
                if has_next_row:
                    rec(j + 1, mask_out | (1 << j))
                if j + 1 < W and row[j + 1] != '#' and not ((mask_in >> (j + 1)) & 1):
                    rec(j + 2, mask_out)
            rec(0, 0)
        dp = ndp

    print(dp.get(0, 0) % MOD)


solve()
計算量: 各行につき到達可能な mask の個数を $M \le 2^W$ として $O(H \cdot M \cdot W)$。$W \le 12$ なら十分高速。

Step-by-Step 解説

1状態設計
dp[mask] は「現在処理しようとしている行の各列のうち、上の行からの縦ドミノで強制的に埋まっている列の集合」をキーとする辞書。初期状態は dp={0:1}。
21行分の遷移を再帰で列挙
壁マス／上から埋まっているマス／空きマス（縦ドミノで下に伸ばす・横ドミノで消費する）の場合分けを行う。
3最終行の判定
全行処理後、mask==0 の dp 値のみが正しい完全被覆に対応する。

よくあるミス

ミス原因正しい書き方
最終行の後で mask≠0 の値も答えに加算「盤外にはみ出す縦ドミノ」の存在を見落とす答えは必ず dp.get(0,0) のみ採用
壁のマスに縦ドミノが伸びてきたケースを弾かない壁は「存在しないマス」であることを忘れる壁かつ mask_in のビットが立っていれば即座に return
横ドミノの相手マスの状態確認漏れ境界・状態チェックの漏れj+1<W かつ壁でなくかつ mask_inビットが0であることを確認
空きマス数が奇数でも全探索してTLE早期打ち切りをしない事前に偶奇をチェックし奇数なら0を出力してもよい

次のステップ

  • 発展: L字トロミノ（3マス1枚）を許す敷き詰め数え上げへの拡張
  • 発展: $W$ が小さく $H$ が非常に大きい場合、行の遷移を行列とみなして行列累乗で高速化
  • 次回予告: Gale-Ryser定理（二部次数列の実現可能性判定）

自己評価

自分の回答

気づき・メモ