接着剤の精進日記

競プロでの精進や研究に関係したことを書いていきます。

トップ > AtCoderBeginnerContest > AtCoder Beginner Contest 276（ABC276）

AtCoder Beginner Contest 276（ABC276）

AtCoderBeginnerContest AtCoderBeginnerContest276 ABC ABC276

atcoder.jp

A - Rightmost

for文で a が出てきたら答えのindexを更新していく

提出コード

void solve() {
    string S;
    cin >> S;
    int idx = -1;
    REP(i, S.size()) if (S[i] == 'a') idx = i + 1;
    cout << idx << endl;
}

B - Adjacency List

隣接リストを作り、各頂点ごとにソートをする

提出コード

void solve() {
    int N, M;
    cin >> N >> M;
    vector<vector<int>> g(N);
    REP(i, M) {
        int a, b;
        cin >> a >> b;
        --a, --b;
        g[a].emplace_back(b);
        g[b].emplace_back(a);
    }
    REP(i, N) {
        sort(ALL(g[i]));
        cout << g[i].size();
        for (auto &x : g[i])
            cout << " " << x + 1;
        cout << endl;
    }
}

C - Previous Permutation

prev_permutation を使用する

提出コード

void solve() {
    int N;
    cin >> N;
    vector<int> P(N);
    REP(i, N) cin >> P[i];

    prev_permutation(ALL(P));
    for (auto x : P)
        cout << x << " ";
    cout << endl;
}

D - Divide by 2 or 3

$ A $ のgcdを求め、全体をgcdで割っておく
$ A_i $ を $ 2 $ と $ 3 $ で割れるだけ割っていき、割った回数を答えに加算する
上記の操作を行ったあとに $ a_i \neq 1 $ のとき答えは -1 となる

提出コード

void solve() {
    int N;
    cin >> N;
    vector<ll> a(N);
    ll g = 0;
    REP(i, N) {
        cin >> a[i];
        g = gcd(g, a[i]);
    }
    ll ans = 0;
    REP(i, N) {
        a[i] /= g;
        while (a[i] % 2 == 0) {
            a[i] /= 2;
            ans++;
        }
        while (a[i] % 3 == 0) {
            a[i] /= 3;
            ans++;
        }
        if (a[i] != 1) {
            cout << -1 << endl;
            return;
        }
    }
    cout << ans << endl;
}

E - Round Trip

S の上下四方向から2点を選び、始点と終点とする
始点から終点まで辿り着けるかをBFSなどで判定し辿り着けるならYes

提出コード

void solve() {
    int H, W;
    cin >> H >> W;
    vector<string> C(H);
    REP(i, H) cin >> C[i];
    int sh = 0, sw = 0;
    REP(i, H) REP(j, W) if (C[i][j] == 'S') { sh = i, sw = j; }
    using T = tuple<int, int, int>;
    queue<T> q;
    vector dist(4, vector(H, vector(W, INF)));
    REP(d, 4) {
        dist[d][sh][sw] = 0;
        int h = sh + dx[d];
        int w = sw + dy[d];
        if (h < 0 or h >= H or w < 0 or w >= W or C[h][w] == '#') continue;
        dist[d][h][w] = 1;
        q.emplace(d, h, w);
    }
    while (!q.empty()) {
        auto [sd, h, w] = q.front();
        q.pop();
        REP(d, 4) {
            int nh = h + dx[d];
            int nw = w + dy[d];
            if (nh < 0 or nh >= H or nw < 0 or nw >= W or C[nh][nw] == '#') continue;
            if (dist[sd][nh][nw] == INF) {
                dist[sd][nh][nw] = dist[sd][h][w] + 1;
                q.emplace(sd, nh, nw);
            }
        }
    }
    bool ok = true;
    REP(i, 4) REP(j, 4) if (i != j) {
        int jh = sh + dx[j];
        int jw = sw + dy[j];
        if (jh < 0 or jh >= H or jw < 0 or jw >= W or C[jh][jw] == '#') continue;
        if (dist[i][jh][jw] < INF) {
            cout << "Yes" << endl;
            return;
        }
    }
    cout << "No" << endl;
}

F - Erase Subarrays

$ \max(x,y) $ の総和を保持し、$ K = i $ 回目の場合には $ i ^ 2 $ で総和を割った値が答えになる
$ A_i $ を追加したとき、新たに増える組み合わせとして $ \max(A_i, A_i) $ 、$ \max(A_i, x) (x \leq A_i) $、$ \max(A_i, y) (A_i \lt y ) $ のパターンとなる
$ \max(A_i, x) (x \leq A_i) $ は $ A_i $ 以下の $ x $ の個数を、$ \max(A_i, y) (A_i \lt y ) $ は $ A_i $ より大きい $ y $ の総和を求めることができればいいので、BITなどでこれらを管理する

提出コード

void solve() {
    int N;
    cin >> N;
    vector<int> A(N);
    REP(i, N) cin >> A[i];
    BIT<mint> bit_cnt(202020), bit_sum(202020);
    mint ans = 0;
    REP(i, N) {
        ans += A[i];
        ans += bit_cnt.sum(0, A[i]) * A[i] * 2;
        ans += bit_sum.sum(A[i], 202020) * 2;
        bit_cnt.add(A[i], 1);
        bit_sum.add(A[i], A[i]);
        cout << ans / (i + 1) / (i + 1) << endl;
    }
}