AtCoder Beginner Contest 429 【ABC429】A~D

AtCoder Beginner Contest 429 に参加しました。
パフォーマンス 994
レーティング 1138 → 1124 (-14) となりました。
ペナの多さが課題です。

A - Too Many Requests

問題文の通りに実装すればよいです。

A.cpp

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

int main() {
    int N, M;
    cin >> N >> M;
    for (int i = 0; i < N; i++) {
        if (i < M) cout << "OK" << endl;
        else cout << "Too Many Requests" << endl;
    }
}

B - N - 1

$S = \displaystyle \sum_{k = 1}^N A_k$ とします。
$i = 1 \dots N$ について、 $M = S - A_i$ か判定すればよいです。

B.cpp

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

int main() {
    int N, M;
    cin >> N >> M;
    vector<int> A(N);
    int S = 0;
    for (int i = 0; i < N; i++) {
        cin >> A[i];
        S += A[i];
    }

    for (int i = 0; i < N; i++) {
        if (M == S - A[i]) {
            cout << "Yes" << endl;
            return 0;
        }
    }

    cout << "No" << endl;
}

C - Odd One Subsequence

$cnt[i] = (A[k] = i となるようなkの個数)$ とします。
$A[x] = k, A[y] = k$となるような $(x, y)$ の組について、
$A[z] \neq k$ を満たすような $z$ の個数は $(N - 2) - (cnt[k]- 2) = N - cnt[k]$ となります。
$(x, y)$ の選び方は ${}_{cnt[k]} C_2$ となるので、
$(N - cnt[k]) \cdot \, _{cnt[k]} C_2 $ を $k = 1 \cdots N$ まで足し合わせればよいです。

C.cpp

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

int main() {
    int N;
    cin >> N;
    vector<int> cnt(N);
    for (int i = 0; i < N; i++) {
        int A;
        cin >> A;
        A--;
        cnt[A]++;
    }

    auto nC2 = [&](ll M) {return M * (M - 1) / 2;};
    ll ans = 0;
    for (int i = 0; i < N; i++) {
        const ll M = cnt[i];
        ans += nC2(M) * (N - M);
    }

    cout << ans << endl;
}

D - On AtCoder Conference

一人以上立っている地点を昇順に $D_1 \dots D_K$ とし、 $D_i$ にいる人数を $B_i$ とします。
また、$i = 1 \dots K$ について、$B_{i + K} = B_i$ と定め、 $D_{K + 1} = D_1 + M$とします。
区間 $[D_i, D_{i + 1})$ について考えます。
次に人がいる地点は $D_{i + 1}$ なので、全て答えは同じです。
高橋君が止まるときは、初めて $\displaystyle \sum_{k = i + 1}^j B_k \geq C$　となる地点 $B_j$にいるときです。
$j$ は $B$ の累積和を管理することで二分探索によって求めることができます。
よって、区間 $[D_i, D_{i + 1})$ における答えの総和は
$$(D_{i + 1} - D_i) \sum_{k={i + 1}}^j B_k$$
となります。これを $i = 1 \dots K$ まで足し合わせればよいです。

D.cpp

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

int main() {
    ll N, M, C;
    cin >> N >> M >> C;
    vector<ll> A(N), B, D;
    for (int i = 0; i < N; i++) cin >> A[i];

    sort(A.begin(), A.end());
    int now = 1;
    for (int i = 0; i < N - 1; i++) {
        if (A[i] != A[i + 1]) {
            B.push_back(now);
            D.push_back(A[i]);
            now = 1;
        }

        else now++;
    }

    B.push_back(now);
    D.push_back(A.back());
    
    const int K = B.size();
    D.push_back(D[0] + M);
    vector<ll> S(2 * K + 1);
    for (int i = 0; i < 2 * K; i++) S[i + 1] = S[i] + B[i % K];
    
    ll ans = 0;
    for (int i = 0; i < K; i++) {
        int j = lower_bound(S.begin(), S.end(), S[i + 1] + C) - S.begin();
        ans += (D[i + 1] - D[i]) * (S[j] - S[i + 1]);
    }

    cout << ans << endl;
}