AtCoder Beginner Contest 247（ABC247）

atcoder.jp

Bondo416さんのAtCoder Beginner Contest 247での成績：3882位
パフォーマンス：640相当
レーティング：1498→1436 (-62) :(#AtCoder #ABC247 https://t.co/V7Zh2VlNNE

— ボンド@競プロ (@bond_cmprog) April 10, 2022

A - Move Right

二進数を右に1シフトする

提出コード

void solve(){
    string S;
    cin >> S;
    cout << '0' << S[0] << S[1] << S[2] << endl;
}

B - Unique Nicknames

人 $ i $ にあだ名をつけるには、人 $ i $ 以外に $ s_i $ も $ t_i $ も両方とも出現していなければいいのでこれを全探索する

提出コード

void solve(){
    int N;
    cin >> N;
    vector<string> s(N), t(N);
    REP(i,N) cin >> s[i] >> t[i];
    
    REP(i,N){
        int cnt_s = 0;
        int cnt_t = 0;
        REP(j,N) if(i != j){
            if(s[i] == t[j] or s[i] == s[j]) cnt_s++;
            if(t[i] == s[j] or t[i] == t[j]) cnt_t++;
        }
        if(cnt_s and cnt_t){
            cout << "No" << endl;
            return;
        }
    }
    cout << "Yes" << endl;
}

C - 1 2 1 3 1 2 1

再帰関数で実際に作る

提出コード

void solve(){
    int N;
    cin >> N;
    auto f = [&](auto &&self, int n) -> vector<int>{
        if(n==1) return vector<int>(1, 1);
        vector<int> v = self(self, n-1);
        vector<int> res = v;
        res.push_back(n);
        for(auto x : v) res.push_back(x);
        return res;
    };
    for(auto c : f(f, N)) cout << c << " ";
    cout << endl;
}

D - Cylinder

dequeで $ x $ とその個数を管理し、クエリに答える

提出コード

void solve(){
    int Q;
    cin >> Q;
    deque<pair<ll, ll>> dq;
    while(Q--){
        ll q, x, c;
        cin >> q;
        if(q == 1){
            cin >> x >> c;
            dq.push_back({x, c});
        }
        else{
            cin >> c;
            ll sum = 0;
            while(c > 0){
                auto [x, cnt] = dq.front(); dq.pop_front();
                if(c < cnt){
                    sum += x * c;
                    cnt -= c;
                    dq.push_front({x, cnt});
                    break;
                }
                else{
                    sum += x * cnt;
                    c -= cnt;
                }
            }
            cout << sum << endl;
        }
    }
}

E - Max Min

$ i $ より右側で $ Y $ が含まれる区間の最も左側と最も右側（$ l_1, r_1 $ )、 $ X $ が含まれる最も左側と最も左側（$ l_2, r_2 $) を求めることができれば、$ i $ についての答えは $ \max(0, \min(r_1, r_2) - \max(l_1, l_2)) $ となる
$ l, r $ についてはセグ木上の二分探索で求めることができるので、この総和が答え

提出コード

void solve(){
    int N, X, Y;
    cin >> N >> X >> Y;
    vector<int> A(N);
    REP(i,N) cin >> A[i];
    segtree<int, op1, e1> mi(A);
    segtree<int, op2, e2> ma(A);
    ll ans = 0;
    REP(i,N){
        global_mi = Y+1;
        global_ma = X-1;
        int l1 = mi.max_right<g1>(i);
        int l2 = ma.max_right<g2>(i);
        global_mi = Y;
        global_ma = X;
        int r1 = mi.max_right<g1>(i);
        int r2 = ma.max_right<g2>(i);
        ans += max(0, min(r1, r2) - max(l1, l2));
    }
    cout << ans << endl;
}