AtCoder Beginner Contest 230（ABC230）

atcoder.jp

Bondo416さんのAtCoder Beginner Contest 230での成績：1203位
パフォーマンス：1251相当
レーティング：1482→1461 (-21) :(#AtCoder #ABC230 https://t.co/0kFwAUBdNa

— ボンド@競プロ (@bond_cmprog) December 3, 2021

A - AtCoder Quiz 3

$ N \geq 42 $ のとき $ N + 1 $ として、3桁になるまで0埋めしたものを出力

提出コード

void solve(){
    int N;
    cin >> N;
    if(N >= 42) N++;
    string res = to_string(N);
    res = string(3 - (int)res.size(), '0') + res;
    cout << "AGC" << res << endl;
}

B - Triple Metre

oxx を十分な数連結させた文字列の部分列に $ S $ が含まれるかどうかを愚直に判定する

提出コード

void solve(){
    string S;
    cin >> S;
    string T = "";
    int n = S.size();
    REP(i,10000) T += "oxx";
    REP(i,T.size() - S.size() + 1){
        if(T.substr(i, n) == S){
            cout << "Yes" << endl;
            return;
        }
    }
    cout << "No" << endl;
}

C - X drawing

$ (i, j) (P \leq i \leq Q, \; R \leq j \leq S) $ を全探索する
$ (i, j ) $ が黒く塗られるかどうかは、$ A + k = i $ かつ $ B + k = j $、もしくは $ A + k = i $ かつ $ B - k = j $ を満たすような $ k $ が存在すればいい

提出コード

void solve(){
    ll N, A, B, P, Q, R, S;
    cin >> N >> A >> B >> P >> Q >> R >> S;
    for(ll i=P;i<=Q;i++){
        for(ll j=R;j<=S;j++){
            bool ok = false;
            {
                ll k1 = i - A;
                ll k2 = j - B;
                if(k1 == k2){
                    if(max(1LL - A, 1LL - B) <= k1 and k1 <= min(N - A, N - B)) ok = true;
                }
            }
            {
                ll k1 = i - A;
                ll k2 = j - B;
                if(abs(k1) == abs(k2)){
                    if(max(1LL - A, B - N) <= k1 and k1 <= min(N - A, B - 1LL)) ok = true;
                }
            }
            cout << (ok ? '#' : '.');
        }
        cout << endl;
    }
}

D - Destroyer Takahashi

区間スケジューリングの要領でソートをしてから条件を満たす間は一つの区間として扱い、そうでない場合は答えを1加算して同様の処理を行う

提出コード

void solve(){
    ll N, D;
    cin >> N >> D;
    vector<pair<ll, ll>> lr;
    REP(i,N){
        ll l, r;
        cin >> l >> r;
        lr.emplace_back(r, l);
    }
    sort(ALL(lr));
    ll pre = -1;
    ll ans = 0;
    for(auto [r, l] : lr){
        // dumps(l, r);
        if(pre == -1){
            pre = r;
            continue;
        }
        if(l <= pre + D - 1) continue;
        ans++;
        pre = r;
    }
    if(pre > -1) ans++;
    cout << ans << endl;
}

E - Graph Destruction

$ \sum_{i=1} ^ N \lfloor \frac{N}{i} \rfloor = 2 \sum_{i=1} ^k \lfloor \frac{N}{i} \rfloor - k^2 ( k = \lfloor \sqrt{N} \rfloor ) $ が成り立つので、これを求める

math.stackexchange.com

提出コード

void solve(){
    ll N;
    cin >> N;
    ll sum = 0;
    ll i = 1;
    for(i=1;i*i<=N;i++){
        sum += N / i;
    }
    i--;
    cout << 2 * sum - i * i << endl;
}