接着剤の精進日記

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

トップ > AtCoderBeginnerContest > AtCoder Beginner Contest 250（ABC250）

AtCoder Beginner Contest 250（ABC250）

AtCoderBeginnerContest AtCoderBeginnerContest250 ABC ABC250

atcoder.jp

A - Adjacent Squares

上下左右の4方向にマスがあるかどうかを調べる

提出コード

void solve(){
    int H, W, R, C;
    cin >> H >> W >> R >> C;
    --R, --C;
    int ans = 0;
    REP(d,4){
        int nh = R + dx[d];
        int nw = C + dy[d];
        if(nh < 0 or nh >= H or nw < 0 or nw >= W) continue;
        ans++;
    }
    cout << ans << endl;
}

B - Enlarged Checker Board

$ A = B = 1 $ のとき、.か#かどうかは $ i + j $ の偶奇で決まる
それ以外の場合でも同様で、$ i + j $ ごとに $ A \times B $のマスを出力していく

提出コード

void solve(){
    int N, A, B;
    cin >> N >> A >> B;
    vector fi(A * N, vector<char>(B * N));
    int p = 0;
    REP(i,N){
        REP(h,A){
            REP(j,N) {
                REP(w,B){
                    fi[i*A+h][j*B+w] = ((i + j) % 2 == 0 ? '.' : '#');
                }
            }
        }
    }
    REP(i,A*N){
        REP(j,B*N) cout << fi[i][j];
        cout << endl;
    }
}

C - Adjacent Swaps

整数 $ i $ のボールが今どこにあるかと、実際に並んでいる $ a $ の情報を持っておき、各クエリで実際にswapを行う

提出コード

void solve(){
    int N, Q;
    cin >> N >> Q;
    vector<int> x(Q);
    vector<int> A(N), idx(N);
    iota(ALL(A), 0);
    iota(ALL(idx), 0);
    REP(i,Q){
        cin >> x[i];
        --x[i];
        int idx1 = idx[x[i]];
        int idx2 = (idx1 == N - 1 ? idx1 - 1 : idx1 + 1);
        int right = A[idx2];
        swap(A[idx1], A[idx2]);
        swap(idx[x[i]], idx[right]);
    }
    REP(i,N) cout << A[i] + 1 << " ";
    cout << endl;
}

D - 250-like Number

素数 $ p $ を決めると、条件に当てはまる素数 $ q $ には単調性があるので二分探索で求めることができる
そのため素数をエラトステネスの篩などで予め求めておけばいい

提出コード

void solve(){
    ll N;
    cin >> N;
    SieveOfEratosthenes<ll> sieve(1010101);
    vector<ll> cum(1010102);
    REP(i,1010101) cum[i+1] = cum[i] + sieve.is_prime[i];
    ll ans = 0;
    for(ll p : sieve.prime){
        if(p > N) break;
        ll l = -1, r = (int)sieve.prime.size() - 1;
        while(r - l > 1){
            ll m = (l + r) >> 1;
            ll q = sieve.prime[m];
            if(q * q * q > N / p) r = m;
            else l = m;
        }
        cerr << p << " " << l << " " << r << endl;
        if(l < 0) continue;
        if(p >= sieve.prime[l]) continue;
        ans += cum[sieve.prime[l]] - cum[p];
        cerr << ans << endl;
    }
    cout << ans << endl;
}

E - Prefix Equality

ある整数 $ i $ が集合に含まれるかどうかをZobrist Hashで管理する
各整数ごとにHashを割り当てておき、追加されるときにそのXorを取ればその値が一致するかどうかで集合に含まれる要素の一致を判定することができる
任意の区間クエリだと最初勘違いしていたので無駄にMoを使って解いた

提出コード

void solve(){
    int N;
    cin >> N;
    vector<int> a(N), b(N);
    Compress<int> cmp;
    REP(i,N){
        cin >> a[i];
        cmp.add(a[i]);
    }
    REP(i,N){
        cin >> b[i];
        cmp.add(b[i]);
    }
    cmp.build();
    int sz = cmp.size();
    vector<uint32_t> hash(sz);
    REP(i,sz) hash[i] = XorShift();

    int Q;
    cin >> Q;
    vector<int> x(Q), y(Q);

    REP(i,Q) cin >> x[i] >> y[i];
    vector<int> ans1(Q), ans2(Q);
    vector<int> cnt1(sz), cnt2(sz);
    int sum1 = 0, sum2 = 0;
    auto add1 = [&](int idx){
        if(cnt1[cmp.get(a[idx])]++ == 0) sum1 ^= hash[cmp.get(a[idx])];
    };
    auto erase1 = [&](int idx){
        if(--cnt1[cmp.get(a[idx])] == 0) sum1 ^= hash[cmp.get(a[idx])];
    };
    auto out1 = [&](int idx){
        ans1[idx] = sum1;
    };
    auto add2 = [&](int idx){
        if(cnt2[cmp.get(b[idx])]++ == 0) sum2 ^= hash[cmp.get(b[idx])];
    };
    auto erase2 = [&](int idx){
        if(--cnt2[cmp.get(b[idx])] == 0) sum2 -= hash[cmp.get(b[idx])];
    };
    auto out2 = [&](int idx){
        ans2[idx] = sum2;
    };
    Mo mo1(N);
    Mo mo2(N);
    REP(i,Q){
        mo1.add(0, x[i]);
        mo2.add(0, y[i]);
    }
    mo1.build(add1, erase1, out1);
    mo2.build(add2, erase2, out2);
    REP(i,Q){
        cout << (ans1[i] == ans2[i] ? "Yes" : "No") << endl;
    }
}