ゆるふわ競プロオンサイト #3 (Div. 1) Yet Another Cake Division

Programming Problems and Competitions :: HackerRank

解法

最初の気付き

まず初手に気づけるかどうかが勝負です。この問題は、以下のような2本の経路のペアを数える問題に言い換えられます。

このように、下と右の移動だけで左上隅→右下隅を結ぶ経路と、上と右の移動だけで左下隅→右上隅を結ぶ経路によって盤面が4分割され、それぞれの経路より上か下かの組み合わせで適切に4人を割り当てた場合、この分け方は必ず条件を満たします。これは問題文で列挙されている不等式を1つずつ確認していくと証明できます。逆に問題文の不等式を満たす時、TMとPNの区切り線およびTPとMNの区切り線はそれぞれこのような経路になることも示せます。

よってスタートはこれら全ての場合の数、つまり 通りです。ただしこれらの中には、ケーキを1つも持たないような人が存在するものが含まれているので、これを除きます。

NG条件の言い換え

ケーキを1つも持たない人が存在する必要十分条件は、2経路が外周のどこかで共有点を持つことです。

外周のどこかで共有点を持った場合、その点が含まれる辺の方向を受け持っている人がケーキを1つも持たなくなります。逆に共有点を持っていない場合は、1経路目がその辺を離れるところと2経路目がその辺に入るところの間に正のマス数が存在するので、必ず1つ以上のケーキを持つことになります。

よって外周に共有点を持つような場合の数を除けば良いです。ここからは場合分けや重複の排除をして地道に数えていくことになります。いくつか方針はありそうですが、私の場合は「四隅がどれも共有点でないもの」と「四隅のどれかが共有点であるもの」に分けて数えました。

四隅がどれも共有点でないもの

外周の辺の上で共有点を持ち、かつ四隅が共有点でないものを数えます。

例えば上側の辺について考えます。他の辺についても、経路の始点終点を入れ替えて考えたり を逆にすることでほぼ同じように計算できます。

上側の辺の共有点のうち一番左の点が、左上隅からどれだけ離れているかを として、 の範囲でこれを全て列挙します。

こうすると、図の青経路は 通りです。赤経路は 通りですが、四隅で共有点を持たない縛りで数えているので、右上隅を通る 通りだけ引きます。この積が除くべき場合の数です。

これを の範囲で全て計算し、上下左右全ての辺について同様に計算して除いていけば良いですが、重複パターンが以下のようなものだけ存在します。

これは上辺を考えた時と下辺を考えた時で2回引かれてしまっています。このようなものが上下で 通り、左右で 通り存在するので、これは足し直します。

四隅のどれかが共有点であるもの

これは、2経路のうち少なくとも片方が「完全なL字」の経路を通るような場合です。

どちらの経路がL字かを選ぶので 通り、L字の方はどちら周りのL字かで 通り、もう片方は任意の経路で 通り。ここから両方がL字のケースが2回数えられているのを引いて、結果としては 通りになります。

これで除くべきケースが全て数えられたので、答えを計算することができます。

ACコード

HackerRankは提出コードが公開されないので、ベタ貼りします。

#include <bits/stdc++.h>
using namespace std;

const int64_t MOD = 1e9+7;
void add(int64_t& a, int64_t b){
    a = (a+b) % MOD;
}
void mul(int64_t& a, int64_t b){
    a = a*b % MOD;
}

vector<int64_t> fact, seq_inv, fact_inv;

void create_fact_mod(int num){
    fact[0] = fact[1] = 1;
    for(int i=2; i<=num; i++) fact[i] = fact[i-1] * i % MOD;
}

void create_seq_inv_mod(int num){
    seq_inv[0] = seq_inv[1] = 1;
    for(int i=2; i<=num; i++) seq_inv[i] = (MOD - MOD/i) * seq_inv[MOD%i] % MOD;
}

void create_fact_inv_mod(int num){
    fact_inv[0] = fact_inv[1] = 1;
    for(int i=2; i<=num; i++) fact_inv[i] = fact_inv[i-1] * seq_inv[i] % MOD;
}

void create_mod_tables(int num){
    fact.resize(num+1);
    seq_inv.resize(num+1);
    fact_inv.resize(num+1);
    create_fact_mod(num);
    create_seq_inv_mod(num);
    create_fact_inv_mod(num);
}

int64_t comb_mod(int n, int k){
    return fact[n] * fact_inv[n-k] % MOD * fact_inv[k] % MOD;
}

int64_t perm_mod(int n, int k){
    return fact[n] * fact_inv[n-k] % MOD;
}

int64_t power_mod(int64_t num, int64_t power){
    int64_t prod = 1;
    num %= MOD;
    while(power > 0){
        if(power&1) prod = prod * num % MOD;
        num = num * num % MOD;
        power >>= 1;
    }
    return prod;
}

int main(){
    int H, W;
    cin >> H >> W;
    create_mod_tables(2e6+10);
    int64_t ans = power_mod(comb_mod(H+W, H), 2);
    for(int j=1; j<W; j++){
        int64_t res = comb_mod(H-1+j, j) * (comb_mod(H+W-j, H)-1) * 2 % MOD;
        add(ans, MOD - res);
    }
    for(int i=1; i<H; i++){
        int64_t res = comb_mod(W-1+i, i) * (comb_mod(H+W-i, W)-1) * 2 % MOD;
        add(ans, MOD - res);
    }
    add(ans, H+W-2);
    int64_t C = comb_mod(H+W, H) * 4 - 4;
    add(ans, MOD - C%MOD);
    cout << ans << endl;
    return 0;
}