M-SOLUTIONS プロコンオープン

結果

　A→B→D→Cと解いて4完。もっと早く解けるべきだとも思うけれど、これくらいが実力だとも感じる。

　直近4回のRatedでは全てレートが上がっていて計+120、Highest更新中。特に訓練しているわけではないので単なる上ブレっぽくはあるが。

A問題

　えー公式なんて覚えてないし難しいかもと思ったけど、なんとか外角の和が360度になることから計算できた。100点のA問題で紙とペンを使うことになるとは。

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

int main() {
    ll N;
    cin >> N;
    cout << 180 * N - 360 << endl;
}

B問題

　最初問題文を読み間違えていて15回分の結果が入力されるのかと思っていた。負けの数を数えた方が簡単だったか。

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

int main() {
    string S;
    cin >> S;
    ll win = 0;
    for (char c : S) {
        if (c == 'o') {
            win++;
        }
    }
    win += 15 - S.size();

    cout << (win >= 8 ? "YES" : "NO") << endl;
}

C問題

　B問題の後は順番通りこれを解いていたんだけど順位表を見ていると早い段階からD問題がC問題と同じかそれ以上に解かれていたので先にそっち行った。Dを解いた後に戻ってきて1時間くらいかけてなんとかAC。解けたはいいが、未だにこの問題に対する良い思考の組み立て方がよくわからない……。

　解けた際の思考順としては

1回勝敗が付くまで対戦して高橋くんが勝つ確率およびその時のゲーム数の期待値を立式
ゲーム数の期待値は $C$ にしか依存しないっぽいと気づく
$N$ 勝 $i$ 敗で終わる確率と、その時の期待ゲーム数を別々に計算して掛け合わせれば良さそう

という感じだった。式をいじり回しているとなんとかなるタイプの問題ではあったか。直前に目にしたぷよぷよについての

30先で30-20になる確率は、50戦30-20の確率とちょっと違う（最後の試合だけ勝敗が確定している）。
— merom686 (@merom686) 2019年5月31日

というツイートに結構助けられた説もある。

　そもそも期待値をこういうふうにMOD取って計算できるのもあまり腑に落ちていないまま適当にやったら通ったという印象。期待値の線形性がうんぬんかんぬんで上手くいくということなんだろうと思っている。以下の解答はコンテスト後書き直したもの。

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

constexpr ll MOD = (ll)1e9 + 7;

ll MODpow(ll n, ll m) {
    ll result = 1;
    while (m) {
        if (m % 2 == 1) {
            result *= n;
            result %= MOD;
        }

        m /= 2;
        n *= n;
        n %= MOD;
    }

    return result;
}

class Combination {
public:
    Combination(ll max_num, ll mod) {
        fact_.resize(max_num + 1, 1);
        inv_fact_.resize(max_num + 1, 1);
        mod_ = mod;
        for (ll i = 2; i <= max_num; i++) {
            fact_[i] = i * fact_[i - 1] % mod_;
            inv_fact_[i] = MODpow(fact_[i], mod_ - 2);
            assert(fact_[i] * inv_fact_[i] % mod_ == 1);
        }
    }
    ll operator()(ll n, ll m) const {
        if (m < 0 || m > n) return 0;
        return fact_[n] * inv_fact_[n - m] % mod_ * inv_fact_[m] % mod_;
    }
private:
    vector<ll> fact_, inv_fact_;
    ll mod_;
};


int main() {
    ll N, A, B, C;
    cin >> N >> A >> B >> C;

    Combination comb(2 * N, MOD);

    //1回どちらかに勝ち負けが付くとしてそれぞれが勝つ確率
    ll probA = A * MODpow(100 - C, MOD - 2) % MOD;
    ll probB = B * MODpow(100 - C, MOD - 2) % MOD;

    //1回勝ち負けが付くまでにかかる期待ゲーム数
    ll one_step = 100 * MODpow(100 - C, MOD - 2) % MOD;

    ll ans = 0;
    for (ll i = 0; i < N; i++) {
        //高橋君がN勝 i敗となる確率
        ll p1 = comb(N - 1 + i, N - 1) * MODpow(probA, N) % MOD * MODpow(probB, i) % MOD;

        //青木君がN勝 i敗となる確率
        ll p2 = comb(N - 1 + i, N - 1) * MODpow(probB, N) % MOD * MODpow(probA, i) % MOD;

        //N + i回の勝ち負けで終わる確率
        ll p = (p1 + p2) % MOD;

        //N + i回勝ち負けが付く場合の期待ゲーム数
        ll exp_game_num = one_step * (N + i) % MOD;

        //答えに足す
        (ans += p * exp_game_num % MOD) %= MOD;
    }

    cout << ans << endl;
}

D問題

　解いている人が多いのでそれほどひねった解法ではないんだろうと思って望んだ。気持ちとして次数が一番大きいノードに一番大きい数を割り当てて、隣接ノードに二番目以降のものを割り当てるということしたくなる。それを実装する。通る。

　解説PDFを見るともっと単純にできたようだ。自分のコードもよく見てみればそういうことになっている(st.empty()が真になるのは最初だけ)のでひどい。考察が甘いから実装が大変になって時間がかかってしまう。

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

int main() {
    ll N;
    cin >> N;
    vector<vector<ll>> connect(N);
    for (ll i = 0; i < N - 1; i++) {
        ll a, b;
        cin >> a >> b;
        a--; b--;
        connect[a].push_back(b);
        connect[b].push_back(a);
    }
    vector<ll> c(N);
    for (ll i = 0; i < N; i++) {
        cin >> c[i];
    }
    sort(c.begin(), c.end(), greater<>());

    struct Node {
        ll node, num;
        bool operator<(const Node& rhs) const {
            return num < rhs.num;
        }
    };

    priority_queue<Node> pq;
    for (ll i = 0; i < N; i++) {
        pq.push({ i, (ll)connect[i].size() });
    }

    vector<bool> used(N, false);

    ll score = 0;
    vector<ll> ans(N);

    stack<ll> st;
    for (ll i = 0; i < N; i++) {
        if (st.empty()) {
            while (true) {
                auto t = pq.top();
                pq.pop();

                if (used[t.node]) {
                    continue;
                }
                used[t.node] = true;

                ans[t.node] = c[i];

                for (auto next : connect[t.node]) {
                    st.push(next);
                }

                break;
            }
        } else {
            while (true) {
                auto t = st.top();
                st.pop();

                if (used[t]) {
                    continue;
                }
                used[t] = true;
                for (auto next : connect[t]) {
                    st.push(next);
                }

                ans[t] = c[i];
                score += c[i];
                break;
            }
        }
    }

    cout << score << endl;
    for (ll i = 0; i < N; i++) {
        cout << ans[i] << " \n"[i == N - 1];
    }
}

E問題

　コンテスト中はほとんど読んでもいなかった。今解いてみたがわからず解説を見てAC。解説の方針でも割り算のところとかこれで上手くいくものかパッとは自信持って断言できないし、例外処理も難しくて何度もしくじりWA出した。難しいですね。

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

constexpr ll MOD = (ll)1e6 + 3;

ll MODpow(ll n, ll m) {
    ll result = 1;
    while (m) {
        if (m % 2 == 1) {
            result *= n;
            result %= MOD;
        }

        m /= 2;
        n *= n;
        n %= MOD;
    }

    return result;
}

int main() {
    ll Q;
    cin >> Q;
    vector<ll> x(Q), d(Q), n(Q);
    for (ll i = 0; i < Q; i++) {
        cin >> x[i] >> d[i] >> n[i];
    }

    constexpr ll max_num = 1e6 + 2;
    vector<ll> fact, inv_fact;
    fact.resize(max_num + 1, 1);
    inv_fact.resize(max_num + 1, 1);
    for (ll i = 2; i <= max_num; i++) {
        fact[i] = i * fact[i - 1] % MOD;
        inv_fact[i] = MODpow(fact[i], MOD - 2);
        assert(fact[i] * inv_fact[i] % MOD == 1);
    }

    for (ll i = 0; i < Q; i++) {
        if (d[i] == 0) {
            cout << MODpow(x[i], n[i]) << endl;
        } else {
            ll x_var_d = x[i] * MODpow(d[i], MOD - 2) % MOD;
            if (x_var_d == 0 || x_var_d + n[i] - 1 >= MOD) {
                cout << 0 << endl;
            } else {
                ll a = x_var_d + n[i] - 1;
                ll b = x_var_d - 1;
                cout << MODpow(d[i], n[i]) * fact[a] % MOD * inv_fact[b] % MOD << endl;
            }
        }
    }
}