AtCoder Beginner Contest 221（ABC221）

atcoder.jp

Bondo416さんのAtCoder Beginner Contest 221での成績：652位
パフォーマンス：1706相当
レーティング：1469→1495 (+26) :)#AtCoder #ABC221 https://t.co/jEkUUIip6h

— ボンド@競プロ (@bond_cmprog) October 2, 2021

A - Seismic magnitude scales

$ A - B $ 回 $ 32 $ を掛ける

提出コード

void solve(){
    int A, B;
    cin >> A >> B;
    ll ans = 1;
    REP(i,A-B) ans *= 32;
    cout << ans << endl;
}

B - typo

隣り合う2文字全てに対しswapをしたものと $ T $ が一致するかを判定

提出コード

void solve(){
    string S, T;
    cin >> S >> T;
    bool ans = false;
    if(S == T) ans = true;
    int N = S.size();
    REP(i,N-1){
        swap(S[i], S[i+1]);
        if(S == T) ans = true;
        swap(S[i], S[i+1]);
    }
    cout << (ans ? "Yes" : "No") << endl;
}

C - Select Mul

各数字を2つのどちらに分けるかをbit全探索をする
分けられたグループ内では、降順ソートすればいい

提出コード

void solve(){
    string S;
    cin >> S;
    int n = S.size();
    auto f = [&](string s) -> ll{
        ll res = 0;
        ll base = 1;
        for(char c : s){
            res += (c - '0') * base;
            base *= 10;
        }
        return res;
    };
    ll ans = 0;
    for(int i=1;i<(1<<n);i++){
        string s = "";
        string t = "";
        REP(j,n){
            if(i >> j & 1) s += S[j];
            else t += S[j];
        }
        sort(s.begin(), s.end());
        sort(t.begin(), t.end());
        chmax(ans, f(s) * f(t));
    }
    cout << ans << endl;
}

D - Online games

座標圧縮をした状態でimos法を行う
$ imos_i $ が $ k $ のとき $ ans_k $ に答えを加算する
提出コード

void solve(){
    int N;
    cin >> N;
    vector<ll> A(N), B(N);
    Compress<ll> cmp;
    cmp.add(0);
    REP(i,N){
        cin >> A[i] >> B[i];
        cmp.add(A[i]);
        cmp.add(A[i] + B[i]);
    }
    cmp.add(LINF);
    cmp.build();
    int sz = cmp.size();
    vector<ll> imos(sz+1);
    REP(i,N){
        imos[cmp.get(A[i])]++;
        imos[cmp.get(A[i] + B[i])]--;
    }
    REP(i,sz) imos[i+1] += imos[i];
    vector<int> ans(N+1);
    for(int i=1;i<sz-1;i++) ans[imos[i]] += cmp[i+1] - cmp[i];
    REP(i,N) cout << ans[i+1] << " ";
    cout << endl;
}

E - LEQ

$ A_0 = A_i $ と固定すると、$ A_i \leq A_k $ を満たすものが右端の候補となる
$ A_k = A_j (i \lt j) $ とすると、$ A_i, A_j $ の間の要素は選んでも選ばなくてもいいので $ 2^{j-i-1} $ 通り答えに寄与する
これは、$ A_j $ の要素数ごとに $ i $ との距離が分かれば求められる
$ 0, 2^0, 2^1, 2^2, \dots, 2^i $ として $ A_i $ の要素ごとに $ 2^i $ を BITに加算する
答えを求めるときは $ A_i $ を除いた $ A_i $ 以上の総和を求めればいい
ただし、$ i $ が1増えるたびに元の距離と$ \frac{1}{2} $ 倍になるのでその分だけ総和を割る必要がある
提出コード

void solve(){
    int N;
    cin >> N;
    vector<ll> A(N);
    Compress<ll> cmp;
    cmp.add(0);
    cmp.add(LINF);
    REP(i,N){
        cin >> A[i];
        cmp.add(A[i]);
    }
    cmp.build();
    int sz = cmp.size();
    BIT<mint> bit(sz+10);
    vector<mint> two(N+1);
    mint cur = 1;
    for(int i=1;i<N;i++){
        two[i] = cur;
        cur *= 2;
    }
    REP(i,N) bit.add(cmp.get(A[i]), two[i]);
    mint ans = 0;
    REP(i,N-1){
        bit.add(cmp.get(A[i]), -two[i]);
        mint sum = bit.sum(cmp.get(A[i]), sz+1);
        if(i > 0) sum /= two[i+1];
        ans += sum;
    }
    cout << ans << endl;
}