接着剤の精進日記

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

トップ > AtCoderBeginnerContest > AtCoder Beginner Contest 328（ABC328）

AtCoder Beginner Contest 328（ABC328）

AtCoderBeginnerContest AtCoderBeginnerContest328 ABC ABC328

atcoder.jp

A - Not Too Hard

題意の通り条件を満たすものの合計を求める

提出コード

void solve() {
    int N, X;
    cin >> N >> X;
    int sum = 0;
    REP(i, N) {
        int A;
        cin >> A;
        if (A <= X) sum += A;
    }
    cout << sum << endl;
}

B - 11/11

$ i, j $ が1種類の数字だけであるかどうかを判定する
to_stringで文字列にしておくと多分楽

提出コード

void solve() {
    int N;
    cin >> N;
    vector<int> D(N);
    REP(i, N) cin >> D[i];
    int ans = 0;
    REP(i, N) {
        int m = i + 1;
        for (int d = 1; d <= D[i]; d++) {
            string md = to_string(m) + to_string(d);
            bool ok = true;
            REP(j, (int)md.size() - 1) {
                if (md[j] != md[j + 1]) ok = false;
            }
            if (ok) ans++;
        }
    }
    cout << ans << endl;
}

C - Consecutive

条件を満たすものの個数の累積和を前計算しておくことで各クエリに対して $ O(1) $ で答えることができる

提出コード

void solve() {
    int N, Q;
    cin >> N >> Q;
    string S;
    cin >> S;
    vector<int> cum(N + 1);
    REP(i, N - 1) cum[i + 1] = cum[i] + (S[i] == S[i + 1]);
    cum[N] = cum[N - 1];
    dump(cum);
    while (Q--) {
        int l, r;
        cin >> l >> r;
        --l, --r;
        cout << cum[r] - cum[l] << endl;
    }
}

D - Take ABC

stackなどで先頭から順に文字を積んでいき、末尾3個は ABC の場合に消去する操作を行い、最終的に残った値を出力すればいい

提出コード

void solve() {
    string S;
    cin >> S;
    vector<char> st;
    for (char c : S) {
        if (st.size() < 2) st.emplace_back(c);
        else {
            if (c == 'C') {
                char c2 = st.back();
                st.pop_back();
                char c1 = st.back();
                st.pop_back();
                if (c1 == 'A' and c2 == 'B') {
                    continue;
                }
                st.emplace_back(c1);
                st.emplace_back(c2);
                st.emplace_back(c);
            }
            else {
                st.emplace_back(c);
            }
        }
    }
    for (auto c : st)
        cout << c;
    cout << endl;
}

E - Modulo MST

全域木なので $ N - 1 $ 本の辺を選ぶ場合のみ考えれば良く、これは最大で $ _{28} C _7 = 1184040 $ 通りなので全探索すれば良い
$ M - (N - 1) $ 個の $ 0 $ と $ N - 1 $ 個の $ 1 $ を並べた配列にnext_permutationを使うとcombinationの列挙ができる

提出コード

void solve() {
    ll N, M, K;
    cin >> N >> M >> K;
    vector<ll> u(M), v(M), w(M);
    REP(i, M) {
        cin >> u[i] >> v[i] >> w[i];
        --u[i], --v[i];
    }
    ll ans = LINF;
    vector<int> cmb;
    REP(i, M - (N - 1)) cmb.emplace_back(0);
    REP(i, N - 1) cmb.emplace_back(1);
    do {
        ll sum = 0;
        UnionFind uf(N);
        bool ok = true;
        REP(i, M) if (cmb[i]) {
            if (uf.issame(u[i], v[i])) {
                ok = false;
                break;
            }
            uf.unite(u[i], v[i]);
            sum += w[i];
            if (sum >= K) sum -= K;
        }
        if (ok) chmin(ans, sum);
    } while (next_permutation(ALL(cmb)));
    cout << ans << endl;
}

F - Good Set Query

$ u - v = d $ という関係式を満たすかどうかは、ある頂点 $ u, v $ の間の距離が $ d $ であるという関係式として考える
そうするとポテンシャル付きUnion Findを使うことで関係式を保存し、新しく関係式を追加する際に過去の関係式と矛盾するかどうかを判定できる

提出コード

void solve() {
    int N, Q;
    cin >> N >> Q;
    PotentializedUnionFind<ll> uf(N);
    vector<int> ans;
    REP(i, Q) {
        int a, b, d;
        cin >> a >> b >> d;
        --a, --b;
        if (uf.issame(a, b)) {
            if (uf.dist(a, b) == d) ans.emplace_back(i + 1);
        }
        else {
            uf.unite(a, b, d);
            ans.emplace_back(i + 1);
        }
    }
    for (auto x : ans)
        cout << x << " ";
    cout << endl;
}