AtCoder Beginner Contest 194（ABC194）

atcoder.jp

びみょー
Bondo416さんのAtCoder Beginner Contest 194での成績：1082位
パフォーマンス：1442相当
レーティング：1510→1503 (-7) :(#AtCoder #ABC194 https://t.co/RLZKYf23GW

— ボンド@競プロ (@bond_cmprog) March 6, 2021

A - I Scream

読解が難しい
問題文のとおり丁寧に場合分け
提出コード

void solve(){
    int A, B;
    cin >> A >> B;
    if(A + B >= 15 and B >= 8) cout << 1 << endl;
    else if(A + B >= 10 and B >= 3) cout << 2 << endl;
    else if(A + B >= 3) cout << 3 << endl;
    else cout << 4 << endl;
}

B - Job Assignment

全探索が間に合うので全探索をする
提出コード

void solve(){
    int N;
    cin >> N;
    vector<int> A(N), B(N);
    REP(i,N) cin >> A[i] >> B[i];
    int ans = INF;
    REP(i,N) REP(j,N){
        if(i == j) chmin(ans, A[i] + B[j]);
        else chmin(ans, max(A[i], B[j]));
    }
    cout << ans << endl;
}

C - Squared Error

$ \sum_{i=2}^{N} \sum_{j=1}^{i-1} (A_i - A_j)^2 = \sum_{i=2}^{N} \sum_{j=1}^{i-1} A_i ^2 + A_j ^2 - 2A_iA_j $ と式変形できるのでこれを求める
$ A_k^2 $ は $ A_i^2, A_j^2 $ と合わせて $ N - 1 $ 回出てくるので $ (N-1)A_k^2 $ 答えに加算する
$ \sum_{i=2}^{N} \sum_{j=1}^{i-1} - 2A_iA_j $ は $ -\sum_{i=2}^{N} 2A_i \sum_{j=1}^{i-1} A_j $ となり累積和を使えば求めることができる
提出コード

void solve(){
    int N;
    cin >> N;
    vector<ll> A(N);
    ll ans = 0;
    REP(i,N){
        cin >> A[i];
        ans += (N-1) * A[i] * A[i];
    }
    ll sum = A[0];
    for(int i=1;i<N;i++){
        ans -= 2LL * A[i] * sum;
        sum += A[i];
    }
    cout << ans << endl;
}

D - Journey

確率 $ \frac{1}{N} $ のものを引くまでの操作の期待値は $ N $ 回となる
今、$ i $ 個の頂点が連結だとすると連結成分が一つ増えるまでの操作の期待値は$ \frac{N}{i} $ 回となる
よって、$ \sum_{i=1}^{N-1} \frac{N}{i} $ が答え
提出コード

void solve(){
    int N;
    cin >> N;
    double ans = 0;
    for(int i=1;i<N;i++){
        ans += N / (double)i;
    }

    printf("%.12lf\n", ans);
}

E - Mex Min

想定解が賢すぎる、区間をsetで管理するやつを使えば結構楽
setだけだと重複要素に対応できないので今見ているM個の区間に出現する要素数を管理すればいい
提出コード

void solve(){
    int N, M;
    cin >> N >> M;
    vector<int> A(N);
    REP(i,N) cin >> A[i];
    vector<int> cnt(1515151);
    RangeSet<int> st;
    REP(i,M){
        cnt[A[i]]++;
        st.insert(A[i]);
    }
    int ans = st.mex();

    for(int i=M;i<N;i++){
        cnt[A[i-M]]--;
        if(cnt[A[i-M]] == 0) st.erase(A[i-M]);
        if(cnt[A[i]] == 0) st.insert(A[i]);
        cnt[A[i]]++;
        chmin(ans, st.mex());
    }
    cout << ans << endl;
}