競プロやります。

競プロを頑張るブログです。

トップ > ABC/ARC > AtCoder Beginner Contest 127

AtCoder Beginner Contest 127

ABC/ARC

D - Integer Cards

https://atcoder.jp/contests/abc127/tasks/abc127_d

方針

A はソートしてよいので、初期状態を A_1 \leq A_2 \leq \dots \leq A_N とします。また操作の順番も入れ替えてよいので、 C_{1} \geq C_{2} \geq \dots \geq C_M とします。

値を書き換えるカードを選ぶときは、最も値が小さく、かつそのとき見ている C よりも値が小さいカードを選ぶべきです。また、いま C は降順にソートされているので、一度 C_i に書き換えたカードが、後の操作で別の値 C_j に書き換えられることはありません。よって、既に n 枚のカードを書き換えたとき、次に書き換える候補となるカードは A_{n+1} となります。

A_{n+1} を書き換える必要が無かった場合、それ以降の A_i は全て A_{n+1} 以上で、しかも以降現れる C は全て今見ている C 以下の値ですので、操作はこの時点で打ち切ることが出来ます。また A_N を書き換えた場合も、以降の書き換えの候補が無くなるため、操作をそこで終了してよいです。

操作を打ち切った時点での A_i の総和を出力すれば答えになります。

ソースコード

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

int main(){
    int N, M;  cin >> N >> M;
    vector<int> A(N+1,0);
    for(int i=1; i<=N; i++){
        cin >> A[i];
    }
    // A を昇順にソート
    sort(A.begin(), A.end()); 

    vector<pair<int,int>> P(M); // P[i] = {B[i], C[i]}
    for(int i=0; i<M; i++){
        cin >> P[i].first >> P[i].second;
    }
    // P を C の降順にソートする
    sort(P.begin(), P.end(), [](const pair<int,int> &a, const pair<int,int> &b){
        return a.second > b.second;
    });

    int n = 0;  // 既に書き換えたカードの枚数
    for(int i=0; i<M; i++){
        int B = P[i].first;
        int C = P[i].second;

        // 最大で B 回カードを書き換える。
        // ただし A[N] を書き換えたら打ち切る。
        // また書き換え候補の A[n+1] が C 以上になっても打ち切る。
        while(B>0 && n+1<=N && A[n+1]<C){
            A[n+1] = C;
            n++;
        }
    }

    ll ans = 0;
    for(int i=1; i<=N; i++){
        ans += A[i];
    }
    cout << ans << endl;
}

E - Cell Distance

https://atcoder.jp/contests/abc127/tasks/abc127_e
制約の N \times M \leq 2 \times 10^5 を N,~M \leq 2 \times 10^5 と勘違いし、最初は途方に暮れていました。

方針

K 個中、2個の駒の置き方を決めたとすると、残りの駒の置き方は W = {}_{NM-2}C_{K-2} 通りです。また、2個の駒の置き方のうち x 座標の差の絶対値が dx となる駒の置き方の数を A_{dx} 通りとし、 A_{dy} を同様に定義します。すると答えは以下で表せます：
　 \displaystyle \sum_{dx=1}^{M-1} A_{dx}\times dx \times W + \sum_{dy=1}^{N-1} A_{dy}\times dy \times W

よって A_{dx},~A_{dy} および W を求めることに帰着しました。

(1) A_{dx}, ~ A_{dy} を求める
dx = 0, dy = 0 のときは答えに影響しないので、 dx > 0, ~dy>0 とします。
x 座標の差が dx となるような 2 マスの列の選び方は、
　 (x_1, x_2) = (1, 1+dx),~(2, 2+dx),~ \dots , (M-dx, M)
の M-dx 通りです。
また x 座標の差は行の選び方には依らないので、行の組み合わせは何でもよく、 N^2 通りです。
よって、以上合わせて A_{dx} = N^2 (M-dx) となります。同様に A_{dy} = M^2 (N-dy) です。

(2) W を求める
W = {}_{NM-2}C_{K-2} = \frac{(NM-2)!}{(K-2)!(NM-K)!} を \pmod{10^9+7} で求めます。

まず (NM-2)! は、 1 から NM - 2 まで順番に掛けながら mod を取ることで求めることが出来ます。

次に 1/(NM-K)! と 1/(K-2)! を \pmod{10^9+7} で求めます。これは 1/(NM-2)! を求めてから、 NM-2, ~ NM-3, \dots, NM-(K+1) のように掛けていけばよいです。肝心の 1/(NM-2)! ですが、フェルマーの小定理：
　 p が素数のとき a^{p-2} = 1/a \pmod{p}
が成り立つことを用いると、 1/(NM-2)! = \{ (NM-2)! \}^{10^9+7 - 2} \pmod{10^9+7} となります。 10^9+5 乗の計算も愚直にやると当然TLEするので、繰り返し二乗法を用います。繰り返し二乗法については、AtCoder Typical Contest 002 - B を見てください。

ソースコード

以下のソースコードでは階乗やその逆数は 1 ~ NM-2 まで全て求めています。

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

ll mod_pow(ll n, ll p, ll mod){
    // 繰り返し二乗法で n^p を mod で割った余りを計算する
    if(p==0) return 1;
    ll res = mod_pow(n*n%mod, p/2, mod);
    if(p%2==1) res = res * n % mod;
    return res;
}

int main(){
    ll N, M, K;
    cin >> N >> M >> K;
    ll mod = 1e9+7;

    vector<ll> fct(N*M-1,1); // fct[n] = n! の mod
    for(ll i=1; i<=N*M-2; i++){
        fct[i] = i * fct[i-1] % mod;
    }

    vector<ll> invfct(N*M-1,1); // invfct[n] = 1/n! の mod
    invfct[N*M-2] = mod_pow(fct[N*M-2], mod-2, mod) % mod;  // 1/(NM-2)! を繰り返し二乗法で求める
    for(ll i=N*M-3; i>=1; i--){
        invfct[i] = (i+1)*invfct[i+1] % mod;
    }

    // Combination(NM-2, K-2) を計算
    ll W = (fct[N*M-2]*invfct[K-2] % mod)*invfct[N*M-K] % mod; 

    ll ans = 0;
    // dx についてのシグマを計算
    for(ll dx=1; dx<M; dx++){
        ll A = (N*N*(M-dx)) % mod;
        ans = (ans + A * dx % mod) % mod;
    }
    // dy についてのシグマを計算
    for(ll dy=1; dy<N; dy++){
        ll A = (M*M*(N-dy)) % mod;
        ans = (ans + A * dy % mod) % mod;
    }

    // 最後に全体に W をかける
    cout << (ans*W)%mod << endl;
}