AtCoder Beginner Contest 215（ABC215）

atcoder.jp

Bondo416さんのAtCoder Beginner Contest 215での成績：2045位
パフォーマンス：1105相当
レーティング：1567→1529 (-38) :(#AtCoder #ABC215 https://t.co/sPTFM0iyCT

— ボンド@競プロ (@bond_cmprog) August 21, 2021

A - Your First Judge

文字列同士の比較を行う
提出コード

void solve(){
    string S;
    cin >> S;
    if(S == "Hello,World!") cout << "AC" << endl;
    else cout << "WA" << endl;
}

B - log2(N)

$ N \gt 0 $ を満たす間 $ 2 $ で割った回数を $ cnt $ とすると $ cnt - 1 $ が答え
提出コード

void solve(){
    ll N;
    cin >> N;
    int cnt = 0;
    while(N > 0){
        N /= 2;
        cnt++;
    }
    cout << cnt-1 << endl;
}

C - One More aab aba baa

next_permutationを使うと $ O(N!) $ で求められる
提出コード

void solve(){
    string S;
    int K;
    cin >> S >> K;
    sort(S.begin(), S.end());
    int cnt = 1;
    do{
        if(cnt == K){
            cout << S << endl;
            return;
        }
        cnt++;
    }while(next_permutation(S.begin(), S.end()));
}

D - Coprime 2

$ A $ に含まれる素因数を全て列挙する
列挙した素因数を含む倍数となる $ x ( 1 \leq x \leq M ) $ にチェックを入れていき、チェックの付かなかったものを出力する
提出コード

void solve(){
    int N, M;
    cin >> N >> M;
    auto spf = smartPrimeFactors(101010);
    vector<int> A(N);
    vector<int> used(101010);
    REP(i,N){
        cin >> A[i];
        auto res = factorize(A[i], spf);
        for(auto &[x, c] : res){
            if(used[x]) continue;
            used[x]++;
            for(int j=x;j<=M;j+=x) used[j] = 1;
        }
    }
    vector<int> ans;
    ans.emplace_back(1);
    for(int i=2;i<=M;i++){
        if(!used[i]) ans.emplace_back(i);
    }
    cout << ans.size() << endl;
    for(auto x : ans) cout << x << endl;
}

E - Chain Contestant

$ dp[i][j] := $ すでに選んだ文字の集合が $ i $ で最後に選んだ文字が $ j $ であるものの数としてbitDPをする
提出コード

void solve(){
    int N;
    string S;
    cin >> N >> S;
    vector dp(1<<10, vector<mint>(11, 0));
    dp[0][10] = 1;
    REP(i,N){
        vector nxt = dp;
        int nxt_s = S[i] - 'A';
        REP(j,1<<10){
            REP(k,11) if(dp[j][k] != 0){
                if(nxt_s != k){
                    if(j >> nxt_s & 1) {}
                    else nxt[j|(1<<nxt_s)][nxt_s] += dp[j][k];
                }
                else{
                    nxt[j][k] += dp[j][k];
                }
            }
        }
        swap(nxt, dp);
    }

    mint ans = 0;
    REP(i,1<<10) REP(j,10) ans += dp[i][j];
    cout << ans << endl;
}

F - Dist Max 2

最小値の最大化を二分探索で求める
$ \min(|x_i - x_j|, |y_i - y_j|) \geq K $ を満たすようなペア $ (i, j) $ が存在するかどうかを判定する
$ x_i \lt x_j $ とすると、条件は $ x_j - x_i \geq K $ かつ $ |y_i - y_j| \geq K $ となる
このとき、$ x_j - K \leq x_i \leq x_j $ を満たすもののうち、$ |y_i - y_j| \geq K $ が存在すればいい
予め $ x $ の昇順にソートしておき、セグメント木などで 条件を満たす $ y_i $ の最大値と最小値を求めればいい
提出コード

void solve(){
    int N;
    cin >> N;
    vector<pair<int, int>> xy(N);
    REP(i,N) cin >> xy[i].first >> xy[i].second;
    sort(xy.begin(), xy.end());
    vector<int> x(N);
    vector<int> y(N);
    REP(i,N){
        x[i] = xy[i].first;
        y[i] = xy[i].second;
    }
    segtree<int, op1, e1> mi(y);
    segtree<int, op2, e2> ma(y);
    auto check = [&](int i, ll m) -> bool{
        int idx = upper_bound(x.begin(), x.end(), x[i] - m) - x.begin();
        if(ma.prod(0, idx) - y[i] >= m) return true;
        if(y[i] - mi.prod(0, idx) >= m) return true;
        return false;
    };
    ll ans = 0;
    REP(i,N){
        ll l = 0, r = LINF;
        while(r - l > 1){
            ll m = (l + r) >> 1;
            if(check(i, m)) l = m;
            else r = m;
        }
        chmax(ans, l);
    }
    cout << ans << endl;
}