ARC032 D問題

難しかった。まず、攻撃力と防御力とか言われて二次元座標に落としこむような発想がない。
二次元配列の累積和はすごい使えそうなのでライブラリ化したい。
また、今までcombinationにはPascalTriangleを使っていたけど、数が大きい時に死ぬので普通に逆元とかでやる奴も大事だなぁと思った。ちなみにこれだと何故か一つだけWA生えるけど気にしない。

int N, K;
const int MAXN = 100001;
const int MAXM = 3001;
const ll mod = (ll)1e9+7;
int MA[MAXN], MD[MAXN];
int B[MAXM][MAXM];

int SUM[MAXM+1][MAXM+1];

ll extgcd(ll a, ll b, ll &x, ll &y) {
    ll g = a;
    if(b != 0){
        g = extgcd(b, a % b, y, x);
        y -= (a / b) * x;
    }else{
        x = 1;
        y = 0;
    }
    return g;
}

ll mod_inverse(ll a, ll m)
{
    ll x, y;
    extgcd(a, m, x, y);
    return (x % m + m) % m;
}

ll combination(int n, int r)
{
    if(n < r)
        return 0;
    if(n-r < r)
        r = n-r;
    ll ret = 1;
    for(int i=0; i<r; i++){
        ret *= (n--);
        ret %= mod;
        ret *= mod_inverse(i+1, mod);
        ret %= mod;
    }
    return ret;
}

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    memset(B, false, sizeof(B));
    cin >> N >> K;
    for(int i=0; i<N; i++){
        cin >> MA[i] >> MD[i];
        B[MA[i]][MD[i]]++;
    }
    //累積和の計算
    {
        memset(SUM, 0, sizeof(SUM));
        for(int i=0; i<MAXM; i++){
            for(int j=0; j<MAXM; j++){
                SUM[i+1][j+1] = -SUM[i][j] + SUM[i+1][j] + SUM[i][j+1] + B[i][j];
            }
        }
    }
    int res;
    {
        auto C = [&](int m){
            for(int i=0; i< MAXM-m; i++){
                for(int j=0; j< MAXM-m; j++){
                    if(SUM[i+m+1][j+m+1]-SUM[i][j+m+1]
                            -SUM[i+m+1][j]+SUM[i][j] >= K)
                        return true;
                }
            }
            return false;
        };
        int low = -1, high = 3000;
        while(high-low > 1){
            int mid = (low+high)/2;
            if(C(mid)){
                high = mid;
            }else{
                low = mid;
            }
        }
        res = high;
    }

    //組み合わせを求める
    ll comb = 0;
    {
        for(int i=0; i< MAXM-res; i++){
            for(int j=0; j< MAXM-res; j++){
                int a = SUM[i+res+1][j+res+1]-SUM[i][j+res+1]-SUM[i+res+1][j]+SUM[i][j];
                int b = SUM[i+res+1][j+res+1]-SUM[i][j+res+1]-SUM[i+res+1][j+1]+SUM[i][j+1];
                int c = SUM[i+res+1][j+res+1]-SUM[i+1][j+res+1]-SUM[i+res+1][j]+SUM[i+1][j];
                int d = SUM[i+res+1][j+res+1]-SUM[i+1][j+res+1]-SUM[i+res+1][j+1]+SUM[i+1][j+1];
                comb += combination(a, K) - combination(b, K) - combination(c, K) + combination(d, K);
                comb %= mod;
                comb += mod;
                comb %= mod;

            }
        }

    }
    cout << res << endl;
    cout << comb << endl;
}