競プロやります。

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

トップ > 企業コンテスト > M-SOLUTIONS プロコンオープン

M-SOLUTIONS プロコンオープン

企業コンテスト

C - Best-of-(2n-1)

https://atcoder.jp/contests/m-solutions2019/tasks/m_solutions2019_c

方針

a = A/100 とし、 b,~c も同様に定義します。

引き分けではない試合が M 回行われたとします。ここで N 回勝利しない方の勝利回数は 0 回から N-1 回までですから、 N \leq M \leq 2N-1 です。

以下のステップで答えを求めます。

  1. 引き分けではない試合がちょうど M 回行われる確率 P_M を求める。
  2. このときの、引き分けを含んだ試合数の期待値 E_M を求める
  3. \sum_{M=N}^{2N-1} P_M \times E_M が答えになる。

(1) P_M を求める
まず、高橋君が 1 回勝つことによって二人の勝敗数が変動する確率を求めます。これは「引き分けが n 回続いたのちに高橋君が勝利する確率」を \sum_{n=0}^{\infty} で足し合わせればよく、
　　 \displaystyle \sum_{n=0}^{\infty} c^{n-1} a = \frac{a}{1-c}
となります。同様にして、青木君が 1 回勝つことで二人の勝敗数が変動する確率は P_b = b/(1-c) です。

また、 M 回目に高橋君が勝利するような勝敗の並び方は、 M 回目は高橋君の勝利で固定でよく、残りは(引き分けを無視して考えると) M-1 回の試合のうち N-1 回が高橋君の勝利となりますから、 {}_{M-1}C_{N-1} 通りとなります。青木君が M 回目に勝利する場合も同様です。

以上まとめると、 M 回目の試合でどちらかが N 回目の勝利となってゲームが終了する確率 P_M は次式で求められます。
　 \displaystyle P_M = {}_{M-1}C_{N-1} \left\lbrace \left( \frac{a}{1-c} \right)^N \left( \frac{b}{1-c} \right)^{M-N} + \left( \frac{a}{1-c} \right)^{M-N} \left( \frac{b}{1-c} \right)^N \right\rbrace

(2) E_M を求める
さて次に、引き分けではない試合がちょうど M 回行われるときの、引き分けを含んだ試合数の期待値 E_M を求める必要があります。これは、引き分けではない試合が 1 回行われるまでの試合数の期待値を M 倍すればよいです。

「引き分けが n 回続いたのちに、どちらかが勝利する」確率は c^n(1-c) で、この時の試合数は n+1 回ですから、引き分けではない試合が 1 回行われるまでの試合数の期待値は、
　 \displaystyle \sum_{n=0}^{\infty} (n+1)c^n (1-c) = \frac{1}{1-c}
となり、
　 \displaystyle E_M = \frac{M}{1-c}
となることがわかりました。


以上合わせて、次式で答えが求まります。
\displaystyle \begin{eqnarray} \sum_{M=N}^{2N-1} P_M \times E_M &=& \sum_{M=N}^{2N-1} {}_{M-1}C_{N-1} \left\lbrace \left( \frac{a}{1-c} \right)^N \left( \frac{b}{1-c} \right)^{M-N} + \left( \frac{a}{1-c} \right)^{M-N} \left( \frac{b}{1-c} \right)^N \right\rbrace \frac{M}{1-c} \\ &=& 100 \times \sum_{M=N}^{2N-1} {}_{M-1}C_{N-1} \left\lbrace \frac{A^N B^{M-N} + B^{M-N} A^N}{(A+B)^{M+1}} \right\rbrace M \end{eqnarray}

シグマの中には階乗やその逆数、ベキの計算が出てきますが、これらは全て O(N) で前計算しておくことができます。するとシグマの計算も O(N) で行えるので、実行時間制限に間に合います。

(2) のシグマの計算

WolframAlphaで求めてもいいのですが、こういう計算をするのは随分久しぶりで懐かしい気持ちになれたので、書いておきます。

　 \displaystyle S_n = \sum_{k=0}^{n} (k+1)c^k = 1 + 2c + 3c^2 + \dots + (n+1)c^n
とします。両辺に c を掛けると
　 \displaystyle cS_n = 0 + c^1 + 2c^2 + \dots + nc^n + (n+1)c^{n+1}
となるので、2式の両辺をそれぞれ引いて、
　 \displaystyle (1-c)S_n = 1 + c + c^2 + \dots + c^n - (n+1)c^{n+1} = \frac{1-c^{n+1}}{1-c} - (n+1)c^{n+1}
ですから、
　 \displaystyle S_n = \frac{1-c^{n+1}}{(1-c)^2} - \frac{(n+1)c^{n+1}}{1-c} \to \frac{1}{(1-c)^2}~(n \to \infty)

よって、
　 \displaystyle \sum_{n=0}^{\infty} (n+1)c^n (1-c) = \frac{1}{1-c}
となります。

ソースコード

#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, A, B, C;
    cin >> N >> A >> B >> C;
    ll mod = 1e9+7;

    // 2N-1 までの階乗を求める
    vector<ll> fct(2*N,1);
    for(ll i=1; i<2*N; i++){
        fct[i] = i * fct[i-1] % mod;
    }

    // 2N-1 までの階乗の逆数を求める
    vector<ll> invfct(2*N,1);
    invfct[2*N-1] = mod_pow(fct[2*N-1], mod-2, mod) % mod;
    for(ll i=2*N-2; i>=1; i--){
        invfct[i] = (i+1)*invfct[i+1] % mod;
    }

    // 1/(A+B) ～ 1/(A+B)^2N を求める
    vector<ll> invAB(2*N+1,1);
    invAB[1] = mod_pow(A+B, mod-2, mod);
    for(int i=1; i<=2*N; i++){
        invAB[i] = invAB[i-1]*invAB[1] % mod;
    }
    
    // A^1 ～ A^N と B^1 ～ B^N を求める
    vector<ll> powA(N+1,1), powB(N+1,1);
    powA[1] = A, powB[1] = B;
    for(int i=1; i<=N; i++){
        powA[i] = powA[i-1] * A % mod;
        powB[i] = powB[i-1] * B % mod;
    }

    // シグマの計算を行う。
    ll ans = 0;
    for(int M=N; M<=2*N-1; M++){
        // 二項係数の部分を計算する
        ll tmp = fct[M-1]*invfct[N-1] % mod;
        tmp = tmp * invfct[M-N] % mod;

        // {} で囲まれた部分
        tmp = tmp * (powA[N]*powB[M-N]%mod + powA[M-N]*powB[N]%mod) % mod; // 分子
        tmp = tmp * invAB[M+1] % mod; // 分母

        tmp = tmp * M % mod;

        ans = (ans + tmp)%mod;
    }

    // 全体を 100 倍
    ans = ans * 100 % mod;
    cout << ans << endl;
}

D - Maximum Sum of Minimum

https://atcoder.jp/contests/m-solutions2019/tasks/m_solutions2019_d

方針

c はソートしてよいので、 c_1 \geq c_2 \geq \dots \geq c_N とします。また、スコアを S とします。

各頂点にどのように c_i を書き込んだとしても、辺上に c_1 が残ることはないため、 S \leq \sum_{i=2}^{N} c_i となります。以下のように頂点に値を書き込んだときに等号が成立するため、これが答えとなります。

まず適当な頂点を根とし、根付き木として考えます。今回は頂点 1 を根とします。

  1. 頂点 1 に c_1 を書き込みます。
  2. 頂点 1 から幅優先探索を行い、到達した頂点に、 c_2, ~ c_3, ~ \dots, c_N を順番に書き込みます。

このとき子の値は必ず親以下のため、親と子を結ぶ頂点には子の値が書き込まれます。根はどの頂点の子でもないので根に書き込んだ値は辺に残りませんが、それ以外の頂点はいずれかの頂点の子であるため、値が辺に書き込まれることになります。よって、 S = \sum_{i=2}^{N} c_i を達成できました。

ソースコード

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

int main(){
    int N;  cin >> N;
    
    // tree[i][j] は 頂点 i とつながる j 番目の頂点
    vector<vector<int>> tree(N, vector<int>());
    for(int i=0; i<N-1; i++){
        int a, b;  cin >> a >> b;
        a--;  b--; // 頂点の番号を 0-indexed とする。
        tree[a].push_back(b);
        tree[b].push_back(a);
    }
    vector<int> c(N);
    for(int i=0; i<N; i++){
        cin >> c[i];
    }
    // c を降順にソートする
    sort(c.begin(), c.end(), greater<int>());

    vector<int> d(N);          // d[i] は頂点 i に書き込む整数
    int idx = 0;               // 探索で到達した頂点に c[idx] を書き込む
    queue<pair<int,int>> que;  // pair<int,int> = {現在の頂点, 現在の頂点の親}
    que.push({0, -1});         // 頂点 0 からスタートする。0 の親は適当に -1 としておく。

    // 幅優先探索
    while(!que.empty()){
        int now = que.front().first;   // 現在の頂点
        int pre = que.front().second;  // 現在の頂点の親
        que.pop();

        d[now] = c[idx];               // 現在の頂点には c[idx] を書き込む
        idx++;

        for(int i=0; i<tree[now].size(); i++){
            // 現在の頂点と直接つながる頂点のうち、親以外へ遷移する
            int nxt = tree[now][i];    
            if(nxt!=pre) que.push({nxt, now});
        }
    }

    int M = 0; // M は c[0] 以外の和
    for(int i=1; i<N; i++){
        M += c[i];
    }

    cout << M << endl;
    for(int i=0; i<N; i++){
        cout << d[i] << " ";
    }cout << endl;
}

E - Product of Arithmetic Progression

https://atcoder.jp/contests/m-solutions2019/tasks/m_solutions2019_e

方針

p = 10^6 + 3 とおきます。

(1) d=0 のとき
x^n を出力します。これは繰り返し二乗法を用いればよいです。

(2) d=1 のとき
このとき求める値は x から x+n-1 までの全ての整数の積になります。

(2-a) x から x+n-1 のなかに p の倍数が含まれるとき
計算は全て \pmod{p} で行えばよいので、 0 を出力します。
x \leq p-1 ですから、 p の倍数が含まれる条件は、 x=0 または p \leq x+n-1 です。

(2-b) それ以外のとき
(x+n-1)!/(x-1)! を \pmod{p} で出力します。
階乗やその逆数の計算をあらかじめ行っておけば O(1) で答えが求められます。 n の範囲は 1 \leq n \leq 10^9 と広いですが、今の条件では x+n-1 < p ですから、 階乗やその逆数の前計算は p-1 まで行っておけば十分です。

(3) d \geq 1 のとき
求める値は d^n (x/d +1)(x/d + 2)\dots(x/d+n-1) となります。よって (2) で x を x/d \pmod{p} で置き換えて計算し、最後に d^n を掛ければよいです。 d^n の計算は (1) と同様に繰り返し二乗法を用いれば出来ます。

ソースコード

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

vector<ll> fct, invfct;

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;
}

ll calc(ll x, ll n, ll mod){
    if(x==0 || x + n - 1 >= mod){
        // (2-a) の場合
        return 0;
    }else{
        // (2-b) の場合
        return fct[x+n-1]*invfct[x-1] % mod;
    }
}

int main(){
    int Q;  cin >> Q;
    ll mod = 1000003;

    // mod-1 までの階乗を求める。
    fct = vector<ll>(mod,1);
    for(int i=1; i<mod; i++){
        fct[i] = fct[i-1] * i % mod;
    }

    // mod-1 までの階乗の逆数を求める。
    invfct = vector<ll>(mod,1);
    invfct[mod-1] = mod_pow(mod-1, mod-2, mod);
    for(int i=mod-2; i>=1; i--){
        invfct[i] = invfct[i+1]*(i+1) % mod;
    }
    
    while(Q--){
        ll x, d, n;  cin >> x >> d >> n;
        if(d==0){
            // (1) の場合。 x^n を計算する。
            cout << mod_pow(x, n, mod) << endl;
        }else if(d==1){
            // (2) の場合。
            cout << calc(x, n, mod) << endl;
        }else{
            // (3) の場合。
            // x を x/d の mod で置き換えて(2)の計算をし、最後に d^n を掛ける。
            x = x * mod_pow(d, mod-2, mod) % mod;
            cout << mod_pow(d, n, mod)*calc(x, n, mod) % mod << endl;
        }
    }
}