接着剤の精進日記

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

Codeforces Round #664 (Div. 2)

codeforces.com

A. Boboniu Likes to Color Balls

 r, g, b, wを使って回文を作るには全ての個数が偶数か、一つだけ奇数であればいい
できる操作を考えると、2回操作をするとその偶奇が元の状態に戻ることがわかる
したがって、操作を行わないもしくは、操作を1回やって回文を作れるかどうかを判定する
提出コード

void solve(){
    ll r, g, b, w;
    cin >> r >> g >> b >> w;
    int odd = 0;
    if(r & 1) odd++;
    if(g & 1) odd++;
    if(b & 1) odd++;
    if(w & 1) odd++;
    if(odd <= 1){
        cout << "Yes" << endl;
        return;
    }
    if(r > 0 && g > 0 && b > 0){
        r--, g--, b--, w += 3;
    }
    odd = 0;
    if(r & 1) odd++;
    if(g & 1) odd++;
    if(b & 1) odd++;
    if(w & 1) odd++;
    if(odd <= 1){
        cout << "Yes" << endl;
    }
    else cout << "No" << endl;
}

B. Boboniu Plays Chess

こどふぉにありがちっぽいやつ
最初一回通ったマス跨げないかと思ってた
実際は跨ぐことができるので初期地点の横方向を全部埋めて端から縦方向を埋めていく
他の人のコード見たら簡潔な実装で出来るっぽくて無駄なことしてた
提出コード

void solve(){
    int n, m, sx, sy;
    cin >> n >> m >> sx >> sy;
    vector<vector<bool>> used(n+1, vector<bool>(m+1));
    vector<P> ans;
    int x = sx, y = sy;
    ans.emplace_back(x, y);
    used[x][y] = true;
    while(y < m){
        y++;
        if(!used[x][y]) ans.emplace_back(x, y);
        used[x][y] = true;
    }
    while(y > 1){
        y--;
        if(!used[x][y]) ans.emplace_back(x, y);
        used[x][y] = true;
    }
    int p = 0;
    for(;y<=m;y++){
        if(y > 1) ans.emplace_back(x,y);
        used[x][y] = true;
        if(p == 0){
            while(x-1 >= 1){
                x--;
                if(!used[x][y]) ans.emplace_back(x, y);
                used[x][y] = true;
            }
            while(x+1 <= n){
                x++;
                if(!used[x][y]) ans.emplace_back(x, y);
                used[x][y] = true;
            }
        }
        else{
            while(x+1 <= n){
                x++;
                if(!used[x][y]) ans.emplace_back(x, y);
                used[x][y] = true;
            }
            while(x-1 >= 1){
                x--;
                if(!used[x][y]) ans.emplace_back(x, y);
                used[x][y] = true;
            }
        }
        p = 1 - p;
    }
    for(auto [x, y] : ans) cout << x << " " << y << endl;
}

C. Boboniu and Bit Operations

想定解が頭良かった
最初はa_iに対してminになるb_jを全探索してそのbitwise ORかなーって思ったけど落ちるケースがありそう
制約的に200^2 \times 2^9が通りそうなのでDPをする
 dp[i][k] :=i番目まで見たときにkが作れるかどうかでDP
提出コード

void solve(){
    int n, m;
    cin >> n >> m;
    vector<int> a(n), b(m);
    REP(i,n) cin >> a[i];
    REP(i,m) cin >> b[i];
    vector<vector<bool>> dp(n+1, vector<bool>(512+10));
    dp[0][0] = true;
    REP(i,n){
        REP(j,m){
            REP(k,512){
                if(dp[i][k]){
                    dp[i+1][k|(a[i]&b[j])] = true;
                }
            }
        }
    }
    REP(i,512){
        if(dp[n][i]){
            cout << i << endl;
            return;
        }
    }
}

D. Boboniu Chats with Du

貪欲でも通ると思うんだけど実装が悪かったのか通らなかった
コンテスト終わってからちらっと見かけた方針で書いたら一発で通って反省
a_ia_i \leq ma_i \gt mに分ける
後者のものを何個取るかで全探索を行い、そのmaxを出力すればいい
後者のものをi(\gt 0)個取った時、取れる前者の個数は、 n - (i-1) \times (d+1) - 1個となる
そのため、両者とも降順にソートをしておき、前者のものは予め累積和をとっておき、 n - (i-1) \times (d+1) - 1個の和をそれぞれで求めればいい
提出コード

void solve(){
    ll n, d, m;
    cin >> n >> d >> m;
    vector<ll> a, b;
    REP(i,n){
        ll num;
        cin >> num;
        if(num <= m) a.emplace_back(num);
        else b.emplace_back(num);
    }
    sort(a.rbegin(), a.rend());
    sort(b.rbegin(), b.rend());
    vector<ll> cum(n+1);
    REP(i,n){
        if(i < size(a)) cum[i+1] = cum[i] + a[i];
        else cum[i+1] = cum[i];
    }
    ll ans = cum[n];
    ll sum = 0;
    for(int i=1;i<=size(b);i++){
        int cnt = n - (i - 1) * (d + 1) - 1;
        if(cnt < 0) break;
        if(i > 0) sum += b[i-1];
        chmax(ans, sum + cum[cnt]);
    }
    cout << ans << endl;
}