公式解説ではDFSですがnext_permutaionで解きます。最後にC++でゴリ押ししたO(3^(HW))の例があります。
考え方
盤面の候補のあり得る初期状態を全列挙することを考え、以下のようなマスの盤面を考えます。
0: 空いているマス 。1が伸びてくる。(a個)
1: 1マスだけ埋まっているマス(b個)
2: 右か下に1マス伸びたいマス(a個)
これを成立する盤面で考えます。
(引用:AtCoderの問題ページより)
これらは以下の初期状態から成立できるものです。
[1, 2, 0] [1, 2, 0] [1, 2, 0] [1, 2, 2] [2, 2, 0] [2, 0, 2]
[2, 2, 2] [2, 2, 0] [2, 0, 2] [2, 0, 0] [0, 1, 2] [2, 1, 0]
[0, 0, 0] [0, 2, 0] [2, 0, 0] [0, 2, 0] [2, 0, 0] [0, 2, 0]
初期状態を与えられたときに成立できるかを判定するには以下のように行います。
- 各行ごとに左から右に見ていきます
- 1がある場合、無視します。1マスのブロックに予約されているからです。
- 2がある場合、右か下に0があるかを確認し、見つからなければNGです。見つかった場合、右から先に使います。使うと決めたマスには1を入れて、他の2がそのマスを使わないようにします。
- 0がある場合、NGです。走査のルールからこのマスは上か左の2によって使われて(1になって)いなければその盤面は成立しません。
次のような初期状態からは成立しません。
[2, 2, 2] [0, 1, 1]
[2, 0, 0] [0, 1, 1]
[0, 0, 1] [1, 2, 2]
- 最初の例は左上の2が右にも下にも伸びられません。
- 2つ目の例は最初に0が出てくるのNGです。この0を埋める2が存在しません
next_permutaionでの全列挙
これらをどのように全列挙するかを考えます。まず、盤面を2次元で管理することを考えます。
[a, b, c]
[d, e, f]
[g, h, i]
という$h\times w$の盤面を[a,b,c,d,e,f,g,h,i]のように長さ$h \times w$の一次元配列表現します。
そして、$0がa個$, $2がa個$, $1がb個$含まれているのが
入力が3 3 4 2なら、[0, 0, 0, 0, 2, 2, 2, 2, 1]のnext_permutationが考えられる図面の全列挙です。
計算量の見積もり
$ {}_{a+a+b} \mathrm{C}_a \times (a+b)\mathrm{C}_a$ 通りの組み合わせに対して、$O(HW)$の操作を行います。
実装
Pythonの場合、next_permutationがないのでnext_permutaionを実装します。(今回はライブラリをお借りしました)
実装(Python/O(1))
# https://strangerxxx.hateblo.jp/entry/20220201/1643705539
def next_permutation(a: list, l: int = 0, r: int = None) -> bool:
if r is None:
r = len(a) - 1
for i in range(r - 1, l - 1, -1):
if a[i] < a[i + 1]:
for j in range(r, i, -1):
if a[i] < a[j]:
a[i], a[j] = a[j], a[i]
p, q = i + 1, r
while p < q:
a[p], a[q] = a[q], a[p]
p += 1
q -= 1
return True
return False
oh, ow, a, b = map(int, input().split())
from itertools import permutations
ans = 0
from copy import deepcopy
se = set()
# 0: 空き, 1: 縦か横, 2: 1マス
opat = [0] * a + [1] * a + [2] * b
pat = [0] * a + [1] * a + [2] * b
while True:
for i in range(a+a+b): pat[i] = opat[i]
can = True
for h in range(oh):
for w in range(ow):
ind = h * ow + w
if pat[ind] == 0:
can = False
break
elif pat[ind] == 2: continue
else:
if w % ow != ow - 1 and pat[ind + 1] == 0:
pat[ind] = 2
pat[ind + 1] = 2
continue
if h != oh - 1 and pat[ind + ow] == 0:
pat[ind] = 2
pat[ind + ow] = 2
continue
can = False
break
if can is False: break
if can:
ans += 1
if next_permutation(opat, 0, len(opat) - 1) is False: break
print(ans)
C++だとO(3^(HM))が通る
という考え方を上記ではnext_permutationであり得る候補だけを全列挙して通しましたがC++では頑張るとあり得ない候補も列挙するO(3^(HM))が通りました。
REP(counter, (int) pow(3, ow * oh)) {
で0,1,2の盤面を全列挙します。