AtCoder Beginner Contest 003 D - AtCoder社の冬

問題

abc003.contest.atcoder.jp

解法

ちょっとアホな方法で通してしまったんですが, 後で紹介します。

まず前提として, この問題は結局「X*Y の長方形を作るように D+L 個の物体を配置する方法は何通りあるのか」というのが求められれば, あとはそれに comb[D+L][D] * (R-X+1) * (C-Y+1) をかけるだけで問題が解けます。

想定解は多分包除原理です。
例えば「X*Y の長方形の上の辺に絶対頂点が存在しない場合」などを考えて, 「X*Y の長方形の好きなところに頂点を並べた場合」から引くことを考えます。ただ, これだと「X*Y の長方形の上と下の辺に絶対頂点が存在しない場合」などを考えてないので数え漏れがあります。こういうのを包除原理でカバーすれば良いだけです。

const ll MOD = 1e9+7;
const int MAX = 1000;
ll comb[2*MAX][2*MAX];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    for (int i = 0; i < 2*MAX; i++) {
        comb[i][0] = 1;
        for (int j = 1; j <= i; j++) {
            comb[i][j] = (comb[i-1][j-1] + comb[i-1][j]) % MOD;
        }
    }
    int R, C, X, Y, D, L;
    cin >> R >> C >> X >> Y >> D >> L;
    ll ans = 0;
    for (int s = 0; s < 1<<4; s++) {
        int h = X, w = Y;
        if (s&1) h--;
        if (s&2) h--;
        if (s&4) w--;
        if (s&8) w--;
        if (h < 0 || w < 0) continue;
        ll tmp = comb[h*w][L+D];
        if (__builtin_popcount(s)%2) tmp = MOD-tmp;
        ans += tmp;
    }
    ans %= MOD;
    (ans *= comb[D+L][L]) %= MOD;
    (ans *= (R-X+1)*(C-Y+1)) %= MOD;
    cout << ans << endl;
    return 0;
}

自分のやった方法は, 上の辺, 下の辺, 右の辺, 左の辺に来る頂点数及び「左上などのかどっこに頂点はあるか」で場合分けして, それぞれの場合の数を求める, ということをやりました。計算量結構ギリギリ。

const ll MOD = 1e9+7;
const int MAX = 1000;

ll comb[2*MAX][2*MAX];

ll calc(int total, int contain, int left, int right) {
    if (left == 1 && right == 1) return comb[total-2][contain-2];
    else if (left == 1 || right == 1) return comb[total-2][contain-1];
    else return comb[total-2][contain];
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    for (int i = 0; i < 2*MAX; i++) {
        comb[i][0] = 1;
        for (int j = 1; j <= i; j++) {
            comb[i][j] = (comb[i-1][j-1] + comb[i-1][j]) % MOD;
        }
    }
    int R, C, X, Y, D, L;
    cin >> R >> C >> X >> Y >> D >> L;
    if (X*Y < D+L) {
        cout << 0 << endl;
        return 0;
    }
    ll ans = 0;
    if (X==1 && Y==1) ans = 1;
    else if (X==1 || Y==1) {
        int Z = max(X, Y);
        if (D+L <= 1) ans = 0;
        else {
            ans = comb[Z-2][D+L-2];
        }
    } else {
        ans = 0;
        int inner = X*Y - (2*X+2*Y) + 4;
        for (int u = 1; u <= Y; u++) for (int d = 1; d <= Y; d++) {
            for (int l = 1; l <= X; l++) for (int r = 1; r <= X; r++) {
                for (int flag = 0; flag < 1<<4; flag++) {
                    int rest = D+L-u-l-d-r;
                    ll tmp = 1;
                    int ul = !!(flag&1);
                    int ur = !!(flag&2);
                    int dl = !!(flag&4);
                    int dr = !!(flag&8);
                    if (ul) rest++;
                    if (ur) rest++;
                    if (dl) rest++;
                    if (dr) rest++;
                    if (rest < 0) continue;
                    (tmp *= comb[inner][rest]) %= MOD;
                    (tmp *= calc(Y, u, ul, ur)) %= MOD;
                    (tmp *= calc(Y, d, dl, dr)) %= MOD;
                    (tmp *= calc(X, l, ul, dl)) %= MOD;
                    (tmp *= calc(X, r, dr, ur)) %= MOD;
                    (ans += tmp) %= MOD;
                }
            }
        }
    }
    (ans *= comb[D+L][D]) %= MOD;
    (ans *= (R-X+1)*(C-Y+1)) %= MOD;
    cout << ans << endl;
    return 0;
}