Hanjo [AtCoder Beginner Contest 196 D]

https://atcoder.jp/contests/abc196/tasks/abc196_d

解説

https://atcoder.jp/contests/abc196/submissions/21119163 恐らく初見だと何から手を付けようかという気持ちになると思う。
制約条件を見るとかなり値が少ないようなので、まずは愚直解を考えてみよう。
今回は愚直解がそのまま答えになるのだが、このようなとりあえず愚直解というのは多くの場面で役に立つ。
（naive解法を作っておけば、あとでoptimized解法を作ったときに手元のランダムテストで役に立つので、
　サクッと時は書いておいてもいいかもしれない。ただし遅い）

愚直解？

今回は長方形のタイルの置き方が確定すれば、正方形のタイルは残りに敷き詰めるだけなので、
長方形のタイルの置き方だけを考えることにする。
どうやってタイルを置くかというのを全探索するのにはDFS、深さ優先探索を使って実装しよう。
探索としては、すべてのマスを左上から見ていき、「おかない」「縦に置く」「横に置く」の3択を選択していく。
選択によっては、長方形のタイルで他のマスが埋まっていくので、マスの埋まり状況(used配列)を管理しながら
遷移をしていく。
全ての選択を終えた後、長方形のタイルを使い切っていれば、それまでの選択によって条件を満たす盤面の状態が
作れているので、組合せが+1される。
これを頑張って実装していく。
自分の実装にインラインでコメントしたので、見てみてほしい。

間に合うの？

全てのマスについて3種類の選択肢があるので、3¹⁶=43046721なので4*10⁶通りで間に合うかなという印象。
実際には、かなりの状態が枝刈りされるのが予想されるので、この状態でギリギリ間に合うかなということは、
まあ、余裕で間に合うだろうという印象。

ちなみに

公式解説にて、「HW≦200はbitDPをしましょう」というヒントがあった。
ちゃんと考えてないけど、たぶん、幅を活用した動的計画法である。

int H, W, A, B;
//---------------------------------------------------------------------------------------------------
bool used[16][16];
int dfs(int x, int y, int a) {
    // 最後まで探索して、長方形のタイルを使い切っているなら、組合せを+1する
    if (H == y) return a == 0;

    // 横の端まで行ったら次の行へ
    if (W == x) return dfs(0, y + 1, a);

    // 既に置かれているなら何もできないので、次のマスへ
    if (used[y][x]) return dfs(x + 1, y, a);

    int res = 0;

    // 縦置き
    if (y + 1 < H && !used[y + 1][x] && 0 < a) {
        used[y][x] = used[y + 1][x] = true;
        res += dfs(x + 1, y, a - 1);
        used[y][x] = used[y + 1][x] = false;
    }

    // 横置き
    if (x + 1 < W && !used[y][x + 1] && 0 < a) {
        used[y][x] = used[y][x + 1] = true;
        res += dfs(x + 1, y, a - 1);
        used[y][x] = used[y][x + 1] = false;
    }

    // 何も置かない
    res += dfs(x + 1, y, a);

    return res;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> H >> W >> A >> B;
    cout << dfs(0, 0, A) << endl;
}