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\)
• \(2A+B = HW\)
• 入力はすべて整数

解法

私がコンテスト中に用いた解法は，長方形のタイルの敷き詰め方のbit全探索です．
長方形のタイルを置く場所は，タイルの向きも考慮すると\(2HW-(H+W)\)通りあります．
例えば\(H=3, W=4\)の場合は，下図のように\(2 \times 3 \times 4 – (3+4) = 17\)通りあります．

長方形のタイルの置き場所は\(2HW-(H+W)\)通りあるので，この中からどの置き場所を使うかをbit全探索します．
bit全探索した結果から，長方形のタイルをちょうど\(A\)枚置き，なおかつ長方形のタイル同士がぶつからないものを抽出すれば答えにたどり着けます．
長方形のタイルの置き場所をすべて決めてしまえば，正方形のタイルの使用枚数と置き方は一意に定まるので，これで答えを出せます．

\(HW \leq 16\)なので長方形のタイルの置き場所は最大で24通り程度となり，C++であればbit全探索しても間に合います．
ただし，実装時に配列を使う場合は配列を宣言する場所に気をつける必要があるかもしれません．

実装例

これが†地獄のbit全探索†です．