接着剤の精進日記

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

トップ > AtCoderBeginnerContest > AtCoder Beginner Contest 294（ABC294）

AtCoder Beginner Contest 294（ABC294）

AtCoderBeginnerContest AtCoderBeginnerContest294 ABC ABC294

atcoder.jp

A - Filter

偶数の入力のみ出力

提出コード

void solve() {
    int N;
    cin >> N;
    REP(i, N) {
        int a;
        cin >> a;
        if (a % 2 == 0) cout << a << " ";
    }
    cout << endl;
}

B - ASCII Art

問題文のとおりに数値を文字列に変換する

提出コード

void solve() {
    int H, W;
    cin >> H >> W;
    REP(i, H) {
        REP(j, W) {
            int a;
            cin >> a;
            if (a == 0) cout << ".";
            else cout << char('A' + a - 1);
        }
        cout << endl;
    }
}

C - Merge Sequences

座圧と同じ操作をする
$ C_k = A_i $、$ C_k = B_j $ を満たす $ k $ を二分探索で求める

提出コード

void solve() {
    int N, M;
    cin >> N >> M;
    vector<int> A(N), B(M);
    vector<int> C;
    REP(i, N) {
        cin >> A[i];
        C.emplace_back(A[i]);
    }
    REP(i, M) {
        cin >> B[i];
        C.emplace_back(B[i]);
    }
    sort(ALL(C));
    REP(i, N) {
        int idx = lower_bound(ALL(C), A[i]) - C.begin();
        cout << idx + 1 << " ";
    }
    cout << endl;
    REP(i, M) {
        int idx = lower_bound(ALL(C), B[i]) - C.begin();
        cout << idx + 1 << " ";
    }
    cout << endl;
}

D - Bank

まだ呼ばれていない番号の集合とすでに受付に呼ばれているが受付に行っていない人の集合それぞれをsetで管理をする

提出コード

void solve() {
    int N, Q;
    cin >> N >> Q;
    set<int> st1, st2;
    REP(i, N) st1.emplace(i);
    while (Q--) {
        int q;
        cin >> q;
        if (q == 1) {
            int x = *st1.begin();
            st1.erase(x);
            st2.emplace(x);
        }
        else if (q == 2) {
            int x;
            cin >> x;
            st2.erase(x - 1);
        }
        else {
            cout << *st2.begin() + 1 << endl;
        }
    }
}

E - 2xN Grid

要素ごとにRangeSetで区間を管理する
予め $ A $ の要素を区間に追加しておく
その後 $ B $ の要素を区間に追加する
$ [l, r) $ の区間を追加したときに追加される区間の増分を $ x $ とすると、その区間には元々 $ r - l - x $ 個の要素があるのでこの総和を求めればいい

提出コード

void solve() {
    ll L, N1, N2;
    cin >> L >> N1 >> N2;
    map<ll, vector<pair<ll, ll>>> mp1, mp2;
    ll sum = 0;
    REP(i, N1) {
        ll v, l;
        cin >> v >> l;
        mp1[v].emplace_back(sum, sum + l);
        sum += l;
    }
    sum = 0;
    REP(i, N2) {
        ll v, l;
        cin >> v >> l;
        mp2[v].emplace_back(sum, sum + l);
        sum += l;
    }
    ll ans = 0;
    for (auto [k, v] : mp1) {
        RangeSet<ll> rst;
        for (auto [l, r] : v) {
            rst.insert(l, r);
        }
        if (mp2.count(k)) {
            for (auto [l, r] : mp2[k]) {
                ll x = rst.insert(l, r);
                ans += r - l - x;
            }
        }
    }
    cout << ans << endl;
}

G - Distance Queries on a Tree

クエリが木上のパスではなく、列であったとすると、1点変更、区間加算ができるセグ木を使用することで求めることができる
木に対してはHL分解を行うことで列と同様にできるのでこれをセグ木を使って求めればいい

提出コード

void solve() {
    int N;
    cin >> N;
    vector<int> v(N - 1), u(N - 1), w(N - 1);
    HLD hld(N);
    REP(i, N - 1) {
        cin >> v[i] >> u[i] >> w[i];
        --v[i], --u[i];
        hld.add_edge(v[i], u[i]);
    }
    hld.build();
    SegTree<ll> seg(
        N, [](ll a, ll b) { return a + b; }, 0);
    REP(i, N - 1) { seg.set(max(hld.vid[v[i]], hld.vid[u[i]]), w[i]); }
    seg.build();
    int Q;
    cin >> Q;
    while (Q--) {
        int q;
        cin >> q;
        if (q == 1) {
            int i;
            ll w;
            cin >> i >> w;
            --i;
            seg.update(max(hld.vid[v[i]], hld.vid[u[i]]), w);
        }
        else {
            int uu, vv;
            cin >> uu >> vv;
            --uu, --vv;
            if (uu > vv) swap(uu, vv);
            ll sum = 0;
            for (auto [l, r] : hld.for_each_edge(uu, vv)) {
                sum += seg.get(l, r);
            }
            cout << sum << endl;
        }
    }
}