Official

D - Hanjo Editorial by en_translator


Since the constraints are small, where \(HW \le 16\), so let us consider searching the way of covering exhaustively.
Starting from the top-left cell, perform DFS of trying placing a square tatami mat, a rectangular tatami mat that sticks out either to the left or below; then we can exhaustively search all the ways of covering.

Now let’s estimate the time complexity.
We have the choices of the top-left cell and the direction of tatami mats, so we have the upper bound of answer of \(2^A\binom{HW}A\).
Since \(HW2^A\binom{HW}A\) is at most \(5 \times 10^7\), so it is fast enough.
In fact, the maximum answer is \(3388\), so it works much faster than estimated.

BONUS: Solve for \(HW ≤ 200\)!

Sample Code (C++)

#include <iostream>
using namespace std;

int H, W, A, B, ans = 0;
void dfs(int i, int bit, int A, int B){
    if(i == H * W) return (void)ans++;
    if(bit & 1 << i) return dfs(i + 1, bit, A, B);
    if(B) dfs(i + 1, bit | 1 << i, A, B - 1);
    if(A){
        if(i % W != W - 1 && ~bit & 1 << (i + 1)) dfs(i + 1, bit | 1 << i | 1 << (i + 1), A - 1, B);
        if(i + W < H * W) dfs(i + 1, bit | 1 << i | 1 << (i + W), A - 1, B);
    }
}
int main(){
    cin >> H >> W >> A >> B;
    dfs(0, 0, A, B);
    cout << ans << endl;
}

Sample Code (Python)

H, W, A, B = map(int, input().split())
ans = 0

def dfs(i, bit, A, B):
    if i == H * W:
        global ans
        ans += 1
        return
    if bit >> i & 1:
        dfs(i + 1, bit, A, B)
        return
    if B:
        dfs(i + 1, bit | 1 << i, A, B - 1)
    if A:
        if i % W != W - 1 and not bit & 1 << (i + 1):
            dfs(i + 1, bit | 1 << i | 1 << (i + 1), A - 1, B)
        if i + W < H * W:
            dfs(i + 1, bit | 1 << i | 1 << (i + W), A - 1, B)

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

posted:
last update: