マスコットの片付け (Mascots - JOI 13 春合宿 2-2)

問題へのリンク

atcoder.jp

問題概要

の収納スペースと、既に片付けられている 個のマスコットの配置が与えられたとき、残りのマスコットの片付ける方法を で割った余りを求める。
ただし、途中で長方形ができるだけ多くなるように並べる。

制約

考察

長方形が完成していなければ、まず長方形を完成させるような並べ方を考える。
これは、最初にできる長方形を求めて、まだ埋まっていないところを埋めていけばよい。
この並べ方は、長方形の内部で埋まっていない部分が 個のとき、 通りある。

長方形が完成したあとは、それを縦方向・横方向に伸ばしていくようにして並べていく。

イメージは上図の通りで、どう求めるかを一旦置いておくと、
dp[上方向の残りの行][下方向の残りの行][左方向の残りの列][右方向の残りの列]
のように dp テーブルを設定すれば求めることができる。
ただ、これは計算量が となるので厳しい。

行方向と列方向をまとめればキーを減らすことができ、
dp[残りの行][残りの列]
と定義できる。
これで計算量を におさえることができる。

今できている長方形の縦の長さを 、横の長さを とする。
長方形を縦方向に伸ばすときの方法は 通りあり、 となる。
同様に、横方向に伸ばすときの方法は 通りあり、 となる。
この要領で dp テーブルを埋めることができる。

この方法はどちらの方向に長方形を伸ばすかで遷移しているので、縦方向と横方向は区別できている。
ただ、上下方向と左右方向の区別はできていないので、最後にその部分の帳尻を合わせる。
テーブルに書かれた値は、縦方向と横方向のあらゆる順番における並べ方の総数であるが、このすべてについて縦方向と横方向は独立に考えることができる。
まず、縦方向について考える。
上方向の残り行数が 個、下方向の残り行数が 個であるとすると、上下の並べ方は ↑ を 個と ↓ を 個の並べ方に帰着できる。
これは二項係数で求めることができるので、前計算しておき二項計算を で求められるようにしておく。( 二項係数の求め方については割愛。)
この前計算により、階乗も で求まる。
横方向についても同様である。

計算量は、二項係数の前計算がボトルネックで、。
ただし、 である。

コード

#include <iostream>
#include <vector>
using namespace std;

template<class T>
inline bool chmax(T& x, T y){
    if(x < y){
        x = y;
        return true;
    }
    return false;
}
template<class T>
inline bool chmin(T& x, T y){
    if(x > y){
        x = y;
        return true;
    }
    return false;
}

constexpr int mod = 1000000007;

struct modint{ /* modint の定義 */ };

template<typename T>
struct Combination{
    // 二項係数の前計算
    // fact(X) で X! の値を返す
    // (n, k) で nCk の値を返す
};

int main(){
    int R, C, N;
    cin >> R >> C >> N;
    int sx = R, sy = C, tx = 0, ty = 0;
    for(int i = 0; i < N; ++i){
        int x, y;
        cin >> x >> y;
        --x, --y;
        chmin(sx, x);
        chmin(sy, y);
        chmax(tx, x);
        chmax(ty, y);
    }
    ++tx, ++ty;
    int H = tx - sx, W = ty - sy;

    // 二項係数の前計算
    Combination<modint> comb(R * C);
    // 長方形を完成させる
    modint ans = comb.fact(H * W - N);
    
    // 縦方向と横方向を区別して dp の計算
    vector<vector<modint>> dp(R - H + 1, vector<modint>(C - W + 1));
    vector<vector<bool>> decided(R - H + 1, vector<bool>(C - W + 1, false));
    dp[0][0] = 1;
    decided[0][0] = true;
    auto MemoRec = [&](auto&& self, int i, int j) -> modint {
        if(decided[i][j])   return dp[i][j];
        modint res = 0;
        if(i > 0)   res += self(self, i - 1, j) * comb.fact(C - j);
        if(j > 0)   res += self(self, i, j - 1) * comb.fact(R - i);
        decided[i][j] = true;
        return dp[i][j] = res;
    };
    ans *= MemoRec(MemoRec, R - H, C - W);

    // 上下方向と左右方向の区別
    ans *= comb(R - H, sx) * comb(C - W, sy);

    cout << ans << endl;
}

雑記

よくありそうな計算量の削減だが、解くのに時間がかかった。
数え上げの問題を素早く解けるようになりたい。
現状、解けても時間がかかりすぎて全然使い物にならない。

AGC は手も足も出なくて悲しすぎる…
Trie は最近理解したんだけど、よく分からなくなってしまった。