Codeforces Round #672 (Div. 2) 参加記

A. Cubes Sorting

すべての要素が異なり、逆順に並んでいるとき、バブルソートは最大で回の操作が必要になります。そうでないとき、それ未満で終わります。

void solve(){
    int N;
    cin >> N;
    vector<ll> a(N);
    rep(i,N)cin >> a[i];
    rep(i,N-1){
        if(a[i] <= a[i+1]){
            cout << "YES" << endl;
            return;
        }
    }
    cout << "NO" << endl;
}

B. Rock and Lever

いつものxorを+と&に変換するやつかと思って式変形して戸惑っていましたが、今回は最上位bitがどうなるかだけに注目すればよいです。　

void solve(){
    int N;
    cin >> N;
    vector<ll> a(N);
    rep(i,N)cin >> a[i];
    sort(all(a));
    vector<ll> cnt(64, 0);
    rep(i,N){
        for(int k = 63; k >= 0; k--){
            if(bit(k)&a[i]){
                cnt[k]++;
                break;
            }
        }
    }
    dump(cnt);
    ll ans = 0;
    rep(k,64)ans += cnt[k] * (cnt[k]-1) / 2;
    cout << ans << endl;
}

C1. Rescue Nibel!

簡単なDPです。

void solve(){
    int N, Q;
    cin >> N >> Q;
    vector<ll> a(N);
    rep(i,N)cin >> a[i];
    ll dp[2] = {0, -INFLL};
    rep(i,N){
        ll nxt[2] = {-INFLL, -INFLL};
        rep(j,2){
            chmax(nxt[j], dp[j]);
            chmax(nxt[j^1], dp[j] + (j ? -a[i]: a[i]));
        }
        rep(j,2)swap(dp[j], nxt[j]);
    }
    cout << max(dp[0], dp[1]) << endl;
}

D. Rescue Nibel!

void solve(){
    ll N, K;
    cin >> N >> K;
    vector<ll> l(N), r(N);
    map<ll,int> mp;
    rep(i,N){
        cin >> l[i] >> r[i];
        mp[l[i]-1]++;
        mp[l[i]]++;
        mp[l[i]+1]++;
        mp[r[i]-1]++;
        mp[r[i]]++;
        mp[r[i]+1]++;
    }
    int idx = 1;
    for(auto &p: mp)p.second = idx++;
    rep(i,N){
        l[i] = mp[l[i]];
        r[i] = mp[r[i]];
    }
    ll M = idx + 5;
    vector<ll> imos(M);
    vector<ll> outs(M);
    rep(i,N){
        imos[l[i]]++;
        imos[r[i]+1]--;
        outs[r[i]]++;
    }
    rep(i,M-1)imos[i+1] += imos[i];
    mint ans = 0;
    rep(i,M){
        ll old = imos[i] - outs[i];
        // 少なくとも一つがnewであるもの　=> 余事象で全部がoldのものを引けばよい
        mint add = C.Comb(imos[i], K);
        add -= C.Comb(old, K); 
        ans += add;
    }
    cout << ans << endl;
}