AtCoder Beginner Contest 233（ABC233） - 接着剤の精進日記

atcoder.jp

Bondo416さんのAtCoder Beginner Contest 233での成績：878位
パフォーマンス：1505相当
レーティング：1528→1526 (-2) :(#AtCoder #ABC233 https://t.co/J2vQwTFhTi
— ボンド@競プロ (@bond_cmprog) December 25, 2021

A - 10yen Stamp

$ \max(0, \lceil \frac{Y - X}{10} \rceil ) $

提出コード

void solve(){
    int X, Y;
    cin >> X >> Y;
    cout << max(0LL, ceil_div(Y - X, 10)) << endl;
}

B - A Reverse

substrなどで反転したい部分の文字列だけを反転させ、残りとくっつける

提出コード

void solve(){
    int L, R;
    string S;
    cin >> L >> R >> S;
    --L, --R;
    string T = S.substr(L, R-L+1);
    reverse(ALL(T));
    REP(i,L) cout << S[i];
    cout << T;
    REP(i,R+1,S.size()) cout << S[i];
    cout << endl;
}

C - Product

制約が全探索でも間に合う制約になっているのでdfsなどで全探索

提出コード

void solve(){
    ll N, X;
    cin >> N >> X;
    vector<vector<ll>> a(N);
    REP(i,N){
        int l;
        cin >> l;
        REP(j,l){
            int b;
            cin >> b;
            a[i].emplace_back(b);
        }
    }
    ll ans = 0;
    auto dfs = [&](auto && self, ll sum, ll cur) -> void{
        if(cur == N){
            if(X == sum) ans++;
            return;
        }
        for(auto b : a[cur]){
            if(cur == 0) self(self, b, cur+1);
            else{
                if(sum > X / b) continue;
                self(self, b * sum, cur+1);
            }
        }
    };
    dfs(dfs, 0, 0);
    cout << ans << endl;
}

D - Count Interval

Zero-sum Ranges
累積和を考えると、$ cum_r - cum_l = K $ を満たす $ l $ が存在すればいい
今、$ r $ 番目を見ているとすると $ cum_l = cum_r - K $ がすでに存在していれば、その個数をカウントしていく

提出コード

void solve(){
    ll N, K;
    cin >> N >> K;
    vector<ll> A(N);
    REP(i,N) cin >> A[i];
    map<ll, ll> mp;
    mp[0] = 1;
    ll ans = 0;
    ll cur = 0;
    REP(i,N){
        cur += A[i];
        dump(cur);
        ans += mp[cur - K];
        mp[cur]++;
    }
    cout << ans << endl;
}

E - Σ[k=0..10¹⁰⁰]floor(X／10^k)

$ i $ 桁目の値は、$ 1, 2, \dots , i $ 桁目に寄与する
各桁に寄与する値を区間和などで求めたあと、下の桁から繰り上がり処理をシミュレートしていく

提出コード

void solve(){
    string X;
    cin >> X;
    reverse(ALL(X));
    int sz = X.size();

    vector<S> v(sz+10);
    lazy_segtree<S, op, e, F, mapping, composition, id> seg(v);

    REP(i,sz){
        int a = X[i] - '0';
        seg.apply(0, i+1, a);
    }
    string ans = "";
    REP(i,sz+5){
        ll a = seg.prod(i, i+1);
        ans += char((a % 10) + '0');
        seg.apply(i+1, i+2, a / 10);
    }
    reverse(ALL(ans));
    bool leading = true;
    for(char c : ans){
        if(c != '0') leading = false;
        if(!leading) cout << c;
    }
    cout << endl;
}

F - Simple Operations on Sequence

与えられたグラフが木だとすると、バブルソートの要領で $ O(N^2) $ でできそう
与えられた辺から全域森を取り、そのグラフの葉の頂点から決めていけばいい

提出コード

void solve(){
    int N;
    cin >> N;
    vector<int> P(N);
    vector<vector<pair<int, int>>> g(N);
    REP(i,N){
        cin >> P[i];
        --P[i];
    }
    int M;
    cin >> M;
    UnionFind uf(N);
    vector<int> deg(N);
    REP(i,M){
        int a, b;
        cin >> a >> b;
        --a, --b;
        if(uf.unite(a, b)){
            g[a].emplace_back(b, i+1);
            g[b].emplace_back(a, i+1);
            deg[a]++;
            deg[b]++;
        }
    }
    vector<int> ans;
    auto dfs = [&](auto && self, int v, int par, int target) -> bool{
        if(P[v] == target) return true;
        for(auto [nv, e] : g[v]){
            if(nv == par) continue;
            if(self(self, nv, v, target)){
                ans.emplace_back(e);
                swap(P[v], P[nv]);
                return true;
            }
        }
        return false;
    };
    vector<int> used(N);
    REP(_,N){
        int idx = -1;
        int mi = INF;
        REP(j,N) if(!used[j] and chmin(mi, deg[j])) idx = j;
        if(!dfs(dfs, idx, -1, idx)){
            cout << -1 << endl;
            return;
        }
        used[idx] = true;
        deg[idx] = 0;
        for(auto [nv, e] : g[idx]) deg[nv]--;
    }
    cout << ans.size() << endl;
    for(auto c : ans) cout << c << " ";
    cout << endl;
}