AtCoder Beginner Contest 281（ABC281）

atcoder.jp

Bondo416さんのAtCoder Beginner Contest 281での成績：1334位
パフォーマンス：1317相当
レーティング：1541→1520 (-21) :(#AtCoder #ABC281 https://t.co/OwHaEYedQ3

— ボンド@競プロ (@bond_cmprog) December 10, 2022

A - Count Down

for文で出力

提出コード

void solve() {
    int N;
    cin >> N;
    for (int i = N; i >= 0; i--)
        cout << i << endl;
}

B - Sandwich Number

条件を満たすかどうかをif文で判定する

提出コード

void solve() {
    string S;
    cin >> S;
    if (S.size() != 8) cout << "No" << endl;
    else if (!('A' <= S[0] and S[0] <= 'Z')) cout << "No" << endl;
    else if (!('A' <= S.back() and S.back() <= 'Z')) cout << "No" << endl;
    else {
        int sum = 0;
        for (int i = 1; i <= (int)S.size() - 2; i++) {
            if ('A' <= S[i] and S[i] <= 'Z') {
                cout << "No" << endl;
                return;
            }
            sum = sum * 10 + (S[i] - '0');
        }
        if (sum >= 100000 and sum <= 999999) cout << "Yes" << endl;
        else cout << "No" << endl;
    }
}

C - Circular Playlist

一周分の総和を求めて、$ T $ をその総和の余りとすると一周分シミュレートするだけで求められる

提出コード

void solve() {
    ll N, T;
    cin >> N >> T;
    vector<ll> A(N);
    ll all = 0;
    REP(i, N) {
        cin >> A[i];
        all += A[i];
    }
    T %= all;
    ll sum = 0;
    REP(i, N) {
        if (A[i] + sum < T) sum += A[i];
        else {
            cout << i + 1 << " " << T - sum << endl;
            return;
        }
    }
}

D - Max Multiple

$ dp[i][j][k] := i $ 番目まで見たときに、 $ j $ 個選んだときの総和が $ k \pmod{D} $ のときの最大値としてDPをする

提出コード

void solve() {
    int N, K, D;
    cin >> N >> K >> D;
    vector<ll> a(N);
    REP(i, N) cin >> a[i];
    vector dp(N + 1, vector(K + 2, vector(D + 1, -1LL)));
    dp[0][0][0] = 0;
    REP(i, N) REP(j, K + 1) REP(k, D + 1) if (dp[i][j][k] != -1) {
        chmax(dp[i + 1][j][k], dp[i][j][k]);
        chmax(dp[i + 1][j + 1][(k + a[i]) % D], dp[i][j][k] + a[i]);
    }
    cout << dp[N][K][0] << endl;
}

E - Least Elements

$ A_i $ の個数とその総和をBIT2本で管理をする
個数を管理しているBIT上で $ [0, r) $ の区間で総和が $ K $ 個以下となる $ r $ は二分探索で求められるので、その範囲の値の総和をもう一つのBITで求める

提出コード

void solve() {
    int N, M, K;
    cin >> N >> M >> K;
    Compress<ll> cmp;
    vector<ll> A(N);
    REP(i, N) {
        cin >> A[i];
        cmp.add(A[i]);
    }
    cmp.add(LINF);
    cmp.build();
    int sz = cmp.size() - 1;
    BIT<ll> bit(sz + 1), bit_sum(sz + 1);
    REP(i, M - 1) {
        bit.add(cmp.get(A[i]), 1);
        bit_sum.add(cmp.get(A[i]), A[i]);
    }
    REP(i, M - 1, N) {
        bit.add(cmp.get(A[i]), 1);
        bit_sum.add(cmp.get(A[i]), A[i]);
        int l = 0, r = sz;
        while (r - l > 1) {
            ll m = (l + r) >> 1;
            if (bit.sum(m) > K) r = m;
            else l = m;
        }
        ll sum = bit_sum.sum(l);
        sum += cmp[l] * max(0LL, K - bit.sum(l));
        cout << sum << " ";
        bit.add(cmp.get(A[i - M + 1]), -1);
        bit_sum.add(cmp.get(A[i - M + 1]), -A[i - M + 1]);
    }
    cout << endl;
}