接着剤の精進日記

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

トップ > AtCoderBeginnerContest > AtCoder Beginner Contest 261（ABC261）

AtCoder Beginner Contest 261（ABC261）

AtCoderBeginnerContest AtCoderBeginnerContest261 ABC ABC261

atcoder.jp

A - Intersection

$ L_1 \leq x \leq R_1 $ かつ $ L_2 \leq x \leq R_2 $ を満たす個数 $ cnt $ を数え、$ \max(0, cnt-1) $ が答え

提出コード

void solve(){
    int l1, l2, r1, r2;
    cin >> l1 >> r1 >> l2 >> r2;
    int cnt = 0;
    REP(i,101) {
        if(l1 <= i and i <= r1 and l2 <= i and i <= r2) {
            cnt++;
        }
    }
    cout << max(0, cnt-1) << endl;
}

B - Tournament Result

問題文の通りに矛盾があるかどうかを全探索で判定をする

提出コード

void solve(){
    int N;
    cin >> N;
    vector<string> S(N);
    REP(i,N) cin >> S[i];
    bool ok = true;
    REP(i,N) REP(j,i+1,N) {
        if(S[i][j] == 'W' and S[j][i] != 'L') ok = false;
        if(S[i][j] == 'L' and S[j][i] != 'W') ok = false;
        if(S[i][j] == 'D' and S[j][i] != 'D') ok = false;
    }
    cout << (ok ? "correct" : "incorrect") << endl;
}

C - NewFolder(1)

mapで文字列が出現した個数をカウントしていく

提出コード

void solve(){
    int N;
    cin >> N;
    map<string, int> mp;
    REP(i,N) {
        string s;
        cin >> s;
        if(mp.count(s))  cout << s << '(' << mp[s] << ')' << endl;
        else cout << s << endl;
        mp[s]++;
    }
}

D - Flipping and Bonus

$ dp[i][j] := i $ 回目のコイントスまで行ったときにカウンタの値が $ j $ である時の最大値としてDPを行う

提出コード

void solve(){
    int N, M;
    cin >> N >> M;
    vector<int> X(N);
    REP(i,N) cin >> X[i];
    vector<int> Y(N+10);
    REP(i,M) {
        int c, y;
        cin >> c >> y;
        Y[c] = y;
    }
    vector dp(N+10, 0LL);
    REP(i,N) {
        vector nxt(N+10, 0LL);
        for(int j=0;j<=i;j++) {
            chmax(nxt[0], dp[j]);
            chmax(nxt[j+1], dp[j] + X[i] + Y[j+1]);
        }
        swap(nxt, dp);
    }
    cout << *max_element(ALL(dp)) << endl;
}

E - Many Operations

bitごとに独立なのでbitごとで考える
操作前のbitが立っている・立っていない場合で $ i $ 回目まで操作したときの結果（そのbitが立っているかいないか）は一意に定まるのでこれを前計算で求めておく
$ i $ 回目のクエリには今の値 $ X $ の立っているbitごとに前計算した値を更新していけばいい

提出コード

void solve(){
    int N, C;
    cin >> N >> C;
    vector<int> T(N), A(N);
    REP(i,N) cin >> T[i] >> A[i];
    vector on(30, vector(N, 0));
    vector off(30, vector(N, 0));
    REP(b,30) {
        int o = 1;
        int x = 0;
        REP(i,N) {
            if(T[i] == 1) {
                o &= (A[i] >> b & 1);
                x &= (A[i] >> b & 1);
            }
            else if(T[i] == 2) {
                o |= (A[i] >> b & 1);
                x |= (A[i] >> b & 1);
            }
            else {
                o ^= (A[i] >> b & 1);
                x ^= (A[i] >> b & 1);
            }
            on[b][i] = o;
            off[b][i] = x;
        }
    }
    int X = C;
    REP(i,N) {
        int tmp = 0;
        REP(j,30) {
            if(X >> j & 1) tmp |= (on[j][i] << j);
            else tmp |= (off[j][i] << j);
        }
        cout << tmp << endl;
        X = tmp;
    }
}

F - Sorting Color Balls

色を気にしない場合のコストは転倒数であるのでこれを求めておく
同じ色の場合はコストが掛からないので同じ色間での転倒数を全体の転倒数から引いていく

提出コード

void solve(){
    int N;
    cin >> N;
    vector<int> C(N), X(N);
    vector<vector<int>> v(303030);
    REP(i,N) cin >> C[i];
    REP(i,N) cin >> X[i];
    BIT<ll> bit(303030);
    ll ans = 0;
    REP(i,N) {
        ll inv = i - bit.sum(X[i]+1);
        ans += inv;
        bit.add(X[i], 1);
    }
    set<int> st;
    REP(i,N) {
        st.insert(C[i]);
        v[C[i]].emplace_back(X[i]);
    }
    for(auto x : st) {
        vector<int> cmp;
        for(auto y : v[x]) cmp.emplace_back(y);
        sort(ALL(cmp));
        cmp.erase(unique(ALL(cmp)), cmp.end());
        BIT<ll> bitx(cmp.size()+1);
        REP(i,v[x].size()) {
            int idx = lower_bound(ALL(cmp), v[x][i]) - cmp.begin();
            ans -= i - bitx.sum(idx+1);
            bitx.add(idx, 1);
        }
    }
    cout << ans << endl;
}