[python] ABC196 D Hanjo

1.方針

まず、並べて実験してみる。

すると、長方形の畳をA枚並べると、正方形の畳の敷き方は一通りに定まることがわかる。

長方形の畳の並べ方は、左上の1メートル四方のスペースから順に敷き詰めていくと考えると、各スペース毎に「横向きに敷く」「縦向きに敷く」「何も敷かない」の3通りある

計算量は3**16だが、再帰が途中で打ち切られるパターンもあるので、間に合いそう。

2.ソースコード
コードの途中でresを初期化しておかないと、resの値が累積的に計算されるので注意。
イメージとしては、再帰の底の値だけを拾ってくるイメージ。

h, w, a, b = map(int, input().split())

used = [[False]*(w) for _ in range(h)]
# print(used)
def recursion(x, y, a):
  if a == 0:
    return 1
  
  if y == h:
    return 0
  
  if x == w:
    return recursion(0, y+1, a)
  
  if used[y][x]:
    return recursion(x+1, y, a)

  res = 0

  # 横向きに敷く
  if x + 1 <= w - 1:
    if not used[y][x+1]:
      used[y][x] = used[y][x+1] = True
      res += recursion(x+2, y, a-1)
      used[y][x] = used[y][x+1] = False
  
  # 縦向きに敷く
  if y + 1 <= h - 1:
    if not used[y+1][x]:
      used[y][x] = used[y+1][x] = True
      res += recursion(x+1, y, a-1)
      used[y][x] = used[y+1][x] = False
  
  # 何も敷かん
  res += recursion(x+1, y, a)

  return res

ans = recursion(0, 0, a)

print(ans)

※resをグローバル関数として、if a== 0:のときに+1する処理でもok
（https://atcoder.jp/contests/abc196/submissions/28797922）