AtCoder Beginner Contest(ABC) 196 D - Hanjo の解説

はじめに

この間のAtCoder Beginner Contest(ABC)194のD問題が解けなかったので、復習を兼ねて簡単な解説を書きます。 使用言語はpythonを想定しています。

D - Hanjo

問題文

縦メートル、横メートルの長方形の部屋があります。

この部屋にメートルメートルの区別できない畳 (長方形のタイル)枚と、メートルメートルの区別できない半畳 (正方形のタイル)枚を敷き詰めます。メートルメートルの畳は縦長にも横長にも使うことができます。

敷き詰める方法は何通りあるでしょうか？

なお、であることが保証されます。 また、回転や反転を行うことで初めて一致するような敷き詰め方は区別します。

制約

• 入力はすべて整数
• 
• 
• 
• 

解答までの道のり

問題文をよく見る

今回の問題文をよく見てまず思うことは、HやWの最大値が小さいということです。 このことから、泥臭い全探索でも正解できそうだということがわかります。

具体的な解法を考える

全探索できそうだとは言いましたが、どうやって全探索をするか、つまり、ありうるタイルの敷き詰め方を網羅するかが問題となります。

ここで、知っている人は深さ優先探索(DFS)が候補に上がってくると思います。（逆に言えば知らないと解けない） DFSをどうやってやるかを考えると、図のように

• 半畳をそのまま置く
• 畳を横に置く
• 畳を縦に置く

という動作を部屋の一番左上から右へ移動しながらやっていくという方法が思いつきます。 （昨日の僕は思いつきませんでした・・・）

今回の問題におけるDFSのイメージ

そして、コードは下のようになります。 コードの解説はコードのコメントアウトにありますが、 DFSの具体的な動作を理解するには、実装してみるのが一番らしいので、 気が向いたら実装してみてください。

def LI(): return list(map(int, input().split()))

H, W, A, B = LI()

used = [[False]*W for _ in range(H)]

def dfs(i, j, a, b):
    # 畳が残っていないときは置けない
    if (a<0 or b<0): return 0
    # 横の座標が部屋の幅を超えたら下に移る
    if j==W:
        j = 0
        i += 1
    # 縦の座標が部屋の高さを超えたら終了
    if i==H: return 1
    # (i, j)がすでに埋まっていたら (i, j+1)の座標に移る
    if used[i][j]: return dfs(i, j+1, a, b)
    
    res = 0
    used[i][j] = True
    # (i, j)に半畳を置くとき
    res += dfs(i, j+1, a, b-1)
    # (i, j)から(i, j+1)にかけて畳を横向きに置くとき
    if j+1<W and used[i][j+1]==False:
        used[i][j+1] = True
        res += dfs(i, j+1, a-1, b)
        # 探索から戻ってきたときにおいていたのを戻す
        used[i][j+1] = False
    # (i, j)から(i+1, j)にかけて畳を縦向きに置くとき
    if i+1<H and used[i+1][j]==False:
        used[i+1][j] = True
        res += dfs(i, j+1, a-1, b)
        # 探索から戻ってきたときにおいていたのを戻す
        used[i+1][j] = False
    # 探索から戻ってきたときにおいていたのを戻す
    used[i][j] = False

    return res

print(dfs(0, 0, A, B))

まとめ

DFSというアルゴリズムを理解した上で、それを応用するという問題が出たということで、個人的には AtCoderの灰・茶と緑・水色の壁を見せつけられたような気がします。 やっぱり実装の経験を積むことが重要ですかね。気長に頑張りたいと思います。