AtCoder Beginner Contest 282（ABC282）

atcoder.jp

A - Generalized ABC

for文で出力

提出コード

void solve() {
    int K;
    cin >> K;
    REP(i, K) { cout << char('A' + i); }
    cout << endl;
}

B - Let's Get a Perfect Score

二重ループですべての組み合わせについて調べる

提出コード

void solve() {
    int N, M;
    cin >> N >> M;
    vector<string> S(N);
    REP(i, N) cin >> S[i];
    int ans = 0;
    REP(i, N) REP(j, i + 1, N) {
        bool ok = true;
        REP(k, M) if (S[i][k] == 'x' and S[j][k] == 'x') ok = false;
        ans += ok;
    }
    cout << ans << endl;
}

C - String Delimiter

直前に見た " が偶数か奇数かのフラグを持つ
奇数のときは括られているので何もせず、偶数のときは括られていないので,を.に置換する

提出コード

void solve() {
    int N;
    string S;
    cin >> N >> S;
    bool enclosed = false;
    REP(i, N) {
        if (S[i] == '"') enclosed ^= 1;
        if (S[i] == ',' and !enclosed) S[i] = '.';
    }
    cout << S << endl;
}

D - Make Bipartite 2

各連結成分ごとに二部グラフかどうかを判定する
このとき一つでも二部グラフではないものがあれば答えは0となる
ある連結成分においては、黒に塗った頂点の数と白に塗った頂点の数をそれぞれ $ B, W $ とすると、最大で $ BW $ の辺が張ることができる
また、2つの二部グラフからそれぞれ頂点を一つずつ選び、その頂点間に辺を貼ったグラフは二部グラフとなるのでそれぞれの連結成分数を $ sz_1, sz_2 $ とすると2つの二部グラフの間には $ sz_1sz_2 $ の辺を張ることができる
よって上記の総和を求め、最初から貼られている辺の数 $ M $ を引けばいい

提出コード

void solve() {
    ll N, M;
    cin >> N >> M;
    vector<vector<int>> g(N);
    UnionFind uf(2 * N);
    UnionFind uf2(N);
    REP(i, M) {
        int u, v;
        cin >> u >> v;
        --u, --v;
        g[u].emplace_back(v);
        g[v].emplace_back(u);
        uf.unite(u, v + N);
        uf.unite(u + N, v);
        uf2.unite(u, v);
    }
    map<int, vector<int>> mp;
    REP(i, N) mp[uf2.root(i)].emplace_back(i);
    ll ans = 0;
    ll cum = 0;
    for (auto [key, vec] : mp) {
        ll cnt = 0;
        for (auto x : vec) {
            if (uf.issame(x, x + N)) {
                cout << 0 << endl;
                return;
            }
            if (uf.issame(x, key)) cnt++;
        }
        ans += ((ll)vec.size() - cnt) * cnt;
        ans += cum * (ll)vec.size();
        cum += vec.size();
    }
    ans -= M;

    cout << ans << endl;
}

E - Choose Two and Eat One

$ 1 \leq i \lt j \leq N $ を満たす整数の組 $ (i, j) $ について、頂点 $ i $、頂点 $ j $ の間に重み $ A_i ^{A_j}, A_j^{A_i} \pmod{M} $ の辺が貼られているグラフを考える
操作を行うことは $ (i, j) $ の辺を選び、全域木を作ることとみなせる
そのため、重みの降順にソートを行いクラスカル法の要領で全域木を作成し、その重みの総和が答え

提出コード

void solve() {
    int N, M;
    cin >> N >> M;
    vector<ll> A(N);
    REP(i, N) cin >> A[i];
    using T = tuple<ll, int, int>;
    vector<T> edge;
    REP(i, N) REP(j, N) if (i != j) {
        ll cost1 = mod_pow(A[i], A[j], M);
        ll cost2 = mod_pow(A[j], A[i], M);
        edge.emplace_back((cost1 + cost2) % M, i, j);
    }
    UnionFind uf(N);
    sort(ALL(edge));
    reverse(ALL(edge));
    ll ans = 0;
    for (auto [c, u, v] : edge) {
        if (uf.unite(u, v)) {
            ans += c;
        }
    }
    cout << ans << endl;
}

F - Union of Two Sets

sparse tableの要領で区間の長さが $ 1, 2, 4, ..., 2^{\lfloor \log_2 N \rfloor} $ の区間を予めすべて作成しておく
$ Table[k][i] := $ インデックスが $ i $ から始まる $ 2^k $ 個の区間の番号として上記の区間に番号をつけておく
区間クエリ $ [l, r) $ に対して $ k = \lfloor \log_2 (r-l) \rfloor $ とすると、$ Table[k][l], Table[k][r-2^k] $ を出力すればいい

提出コード

void solve() {
    int N;
    cin >> N;
    vector<int> LogTable(N + 1);
    REP(i, 2, N + 1) LogTable[i] = LogTable[i >> 1] + 1;
    vector<vector<int>> Table(LogTable[N] + 1, vector<int>(N));
    int idx = 0;
    vector<pair<int, int>> lr;
    REP(i, N) {
        Table[0][i] = idx++;
        lr.emplace_back(i + 1, i + 1);
    }
    for (int k = 1; (1 << k) <= N; k++) {
        for (int i = 0; i + (1 << k) <= N; i++) {
            Table[k][i] = idx++;
            lr.emplace_back(i + 1, i + (1 << k));
        }
    }
    cout << lr.size() << endl;
    for (auto [l, r] : lr)
        cout << l << " " << r << endl;

    int Q;
    cin >> Q;
    while (Q--) {
        int l, r;
        cin >> l >> r;
        --l;
        int k = LogTable[r - l];
        cout << Table[k][l] + 1 << " " << Table[k][r - (1 << k)] + 1 << endl;
    }
}