接着剤の精進日記

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

トップ > AtCoderBeginnerContest > AtCoder Beginner Contest 293（ABC293）

AtCoder Beginner Contest 293（ABC293）

AtCoderBeginnerContest AtCoderBeginnerContest293 ABC ABC293

atcoder.jp

A - Swap Odd and Even

問題文の通りにswapしたものを出力

提出コード

void solve() {
    string S;
    cin >> S;
    int n = S.size();
    REP(i, n / 2) swap(S[2 * i], S[2 * i + 1]);
    cout << S << endl;
}

B - Call the ID Number

シミュレートを行い、呼ばれなかった人の番号を出力

提出コード

void solve() {
    int N;
    cin >> N;
    vector<int> A(N);
    vector<int> used(N);
    REP(i, N) {
        cin >> A[i];
        --A[i];
        if (!used[i]) used[A[i]] = 1;
    }
    vector<int> ans;
    REP(i, N) if (!used[i]) ans.emplace_back(i + 1);
    cout << ans.size() << endl;
    for (auto x : ans)
        cout << x << " ";
    cout << endl;
}

C - Make Takahashi Happy

通ったマスの整数をsetなどで管理をしながら実際にDFSなどで移動経路を全探索する

提出コード

void solve() {
    int H, W;
    cin >> H >> W;
    vector A(H, vector(W, 0));
    REP(i, H) REP(j, W) cin >> A[i][j];
    int ans = 0;
    auto dfs = [&](auto &&self, int h, int w, set<int> st) {
        if (h == H - 1 and w == W - 1) {
            ans++;
            return;
        }
        REP(d, 2) {
            int nh = h + dx[d];
            int nw = w + dy[d];
            if (nh < 0 or nh >= H or nw < 0 or nw >= W) continue;
            if (st.count(A[nh][nw])) continue;
            auto nxt_st = st;
            nxt_st.emplace(A[nh][nw]);
            self(self, nh, nw, nxt_st);
        }
    };
    set<int> st;
    st.emplace(A[0][0]);
    dfs(dfs, 0, 0, st);
    cout << ans << endl;
}

D - Tying Rope

頂点を2倍にしてUnionFindで集合を管理する
制約からある集合について辺の数と頂点の個数が一致しているときサイクルとなるので各集合ごとにこれを確認する
頂点2倍にしなくてもいいらしい

提出コード

void solve() {
    int N, M;
    cin >> N >> M;
    UnionFind uf(2 * N);
    REP(i, N) uf.unite(i, N + i);
    vector<int> a(M), c(M);
    vector<char> b(M), d(M);
    REP(i, M) {
        cin >> a[i] >> b[i] >> c[i] >> d[i];
        --a[i], --c[i];
        int na = (b[i] == 'R' ? a[i] : N + a[i]);
        int nc = (d[i] == 'R' ? c[i] : N + c[i]);
        uf.unite(na, nc);
    }
    set<int> root;
    vector<int> edge(2 * N);
    REP(i, N) {
        root.emplace(uf.root(i));
        edge[uf.root(i)]++;
    }
    REP(i, M) edge[uf.root(a[i])]++;
    int X = 0, Y = root.size();
    for (auto x : root) {
        if (edge[x] == uf.size(x)) {
            X++;
            Y--;
        }
    }
    cout << X << " " << Y << endl;
}

E - Geometric Progression

求める答えは等比数列の和となる
等比数列の和を $ f(A, X, M) $ とすると $ X = 0 $ のとき $ f(A,0,M) = 0 $ となる
$ X $ が奇数のとき、$ f(A, X, M) = 1 + Af(A,X-1,M) $ となる
また、$ X $ が偶数のとき $ f(A,2n, M) = f(A,n,M) + A^n f(A,n,M) $ となるので再帰関数と繰り返し二乗法を用いて求めることができる

提出コード

void solve() {
    ll A, X, M;
    cin >> A >> X >> M;
    cout << sum(1, A, X, M) << endl;
}

G - Triple Index

ある区間 $ [l, r] $ の答えがわかっているとする
その時、区間を $ [ l - 1, r ] $ もしくは $ [l, r + 1] $ にしたときに追加される整数 $ x $ がもともとの区間に含まれる個数を $ cnt $ とするとその答えの差分は $ _{cnt +1 } C _3 - _{cnt} C _3 $ となる
同様に区間を$ [l+1, r] $ もしくは $ [l, r-1] $ としたときの答えも差分計算できる
よって上記をMo’s algorithmを用いることで求めることができる

提出コード

void solve() {
    int N, Q;
    cin >> N >> Q;
    vector<int> A(N);
    REP(i, N) cin >> A[i];
    vector<ll> ans(Q);
    vector<ll> cnt(202020);
    ll num = 0;
    auto add = [&](int idx) {
        num -= cnt[A[idx]] * (cnt[A[idx]] - 1) * (cnt[A[idx]] - 2) / 6;
        cnt[A[idx]]++;
        num += cnt[A[idx]] * (cnt[A[idx]] - 1) * (cnt[A[idx]] - 2) / 6;
    };
    auto erase = [&](int idx) {
        num -= cnt[A[idx]] * (cnt[A[idx]] - 1) * (cnt[A[idx]] - 2) / 6;
        cnt[A[idx]]--;
        num += cnt[A[idx]] * (cnt[A[idx]] - 1) * (cnt[A[idx]] - 2) / 6;
    };
    auto out = [&](int idx) { ans[idx] = num; };
    Mo mo(N);
    REP(i, Q) {
        int l, r;
        cin >> l >> r;
        mo.add(--l, r);
    }
    mo.build(add, erase, out);
    for (auto x : ans)
        cout << x << endl;
}