AtCoder Beginner Contest 306（ABC306）

atcoder.jp

A - Echo

$ S_i $ を2個ずつ出力する

提出コード

void solve() {
    int N;
    string S;
    cin >> N >> S;
    REP(i, N) cout << S[i] << S[i];
    cout << endl;
}

B - Base 2

問題文の通りに計算するだけだが、long long ではオーバーフローするので多倍長整数や unsigned long long を使う

提出コード

void solve() {
    unsigned ll ans = 0;
    REP(i, 64) {
        int a;
        cin >> a;
        if (a) ans += 1uLL << i;
    }
    cout << ans << endl;
}

C - Centers

$ A $ の2番目の要素でソートを行う

提出コード

void solve() {
    int N;
    cin >> N;
    vector<vector<int>> A(N);
    REP(i, 3 * N) {
        int a;
        cin >> a;
        --a;
        A[a].push_back(i);
    }
    vector<int> idx(N);
    iota(ALL(idx), 0);
    sort(ALL(idx), [&](int a, int b) { return A[a][1] < A[b][1]; });
    REP(i, N) cout << idx[i] + 1 << " \n"[i == N - 1];
}

D - Poisonous Full-Course

$ dp[i][j] := i $ 番目までの料理まで選択したときに、高橋くんの状態が $ j $ （お腹を壊しているかどうか）のときに得られた美味しさの和の最大としてDPを行う

提出コード

void solve() {
    int N;
    cin >> N;
    vector<int> X(N), Y(N);
    REP(i, N) cin >> X[i] >> Y[i];
    vector dp(2, -LINF);
    dp[0] = 0;
    REP(i, N) {
        vector ndp(2, -LINF);
        chmax(ndp[0], dp[0]);
        chmax(ndp[1], dp[1]);
        if (X[i] == 0) {
            chmax(ndp[0], dp[0] + Y[i]);
            chmax(ndp[0], dp[1] + Y[i]);
        }
        else {
            chmax(ndp[1], dp[0] + Y[i]);
        }
        swap(dp, ndp);
    }
    cout << max(dp[0], dp[1]) << endl;
}

E - Best Performances

BITでk-th elementの取得と、区間和を求めることで解くことができる
降順に $ k $ 番目の値は昇順に $ N - K $ 番目の値になるのでこの値を取得し、それ以降の区間和を求めればいい

提出コード

void solve() {
    int N, K, Q;
    cin >> N >> K >> Q;
    Compress<int> cmp;
    vector<int> A(N);
    vector<int> X(Q), Y(Q);
    REP(i, Q) {
        cin >> X[i] >> Y[i];
        cmp.add(Y[i]);
        --X[i];
    }
    cmp.add(0);
    cmp.add(2 * INF);
    cmp.build();
    int sz = cmp.size();
    BIT<ll> bit(sz), bit_sum(sz);
    bit.add(0, N);
    ll ans = 0;

    REP(i, Q) {
        int pre = A[X[i]];
        bit.add(cmp.get(pre), -1);
        bit_sum.add(cmp.get(pre), -pre);
        bit.add(cmp.get(Y[i]), 1);
        bit_sum.add(cmp.get(Y[i]), Y[i]);

        int k = bit.kth_element(N - K - 1) - 1;
        ll ans = 0;
        ans += bit_sum.sum(k + 1, sz);
        ans += max(0LL, (K - bit.sum(k + 1, sz))) * cmp[k];
        cout << ans << endl;
        A[X[i]] = Y[i];
    }
}

F - Merge Sets

各$ A _ i $ を昇順に並べ替える操作を予め行っておく
$ A _ {i , j } $ が $ A, B $ の集合の中で答えに寄与する分は、$ A $ の中で 自分より小さいものの個数と、$ B $ の中で自分より小さいものの個数になる
前者は $ j (N - i) $ として求めることができ、後者はBITなどで求めることができる
よって後者を実際に求め最後に前者の値を足した総和が答え

提出コード

void solve() {
    ll N, M;
    cin >> N >> M;
    vector<vector<int>> A(N, vector<int>(M, 0));
    Compress<int> cmp;
    REP(i, N) {
        REP(j, M) {
            cin >> A[i][j];
            cmp.add(A[i][j]);
        }
        sort(ALL(A[i]));
    }
    cmp.build();
    int sz = cmp.size();
    ll ans = 0;
    BIT<int> bit(sz);
    REP(i, N) REP(j, M) bit.add(cmp.get(A[i][j]), 1);
    REP(i, N) {
        REP(j, M) bit.add(cmp.get(A[i][j]), -1);
        REP(j, M) {
            ans += (j + 1) * (N - i - 1);
            ans += bit.sum(0, cmp.get(A[i][j]));
        }
    }
    cout << ans << endl;
}