接着剤の精進日記

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

Codeforces Round #672 (Div. 2)

codeforces.com

A. Cubes Sorting

何もわからなかったので座圧BITで転倒数を求めた
提出コード

void solve(){
    ll n;
    cin >> n;
    vector<ll> a(n);
    map<ll, int> mp;
    REP(i,n){
        cin >> a[i];
        mp[a[i]] = 1;
    }
    int cnt = 1;
    for(auto [v, k] : mp){
        mp[v] = cnt;
        cnt++;
    }
    BIT<ll> bit(n);
    ll res = 0;
    REP(i,n){
        res += i - bit.sum(mp[a[i]]);
        bit.add(mp[a[i]], 1);
    }
    if(res <= n * (n - 1) / 2 - 1) cout << "YES" << endl;
    else cout << "NO" << endl;
}

B. Rock and Lever

こどふぉで割とよく見るやつ
bitが立っている最上位部分が同じならbitwise andはそのままbitwise xorは打ち消し合うのでbitwise andの操作を行ったものが必ず大きくなる
そのためi桁目に立っているbitが最上位のものの個数を管理し、その個数分足していく
提出コード

void solve(){
    int n;
    cin >> n;
    vector<ll> a(n);
    REP(i,n) cin >> a[i];
    vector<ll> bit(40);
    ll ans = 0;
    REP(i,n){
        ll b = 0;
        for(ll j=30;j>=0;j--){
            if(a[i] >> j & 1){
                b = j;
                break;
            }
        }
        ans += bit[b];
        bit[b]++;
    }
    cout << ans << endl;
}

C1. Pokémon Army (easy version)

dp[i][j] :=j個目まで見たとき、次に+を取るならi=1, -を取るならi=0
としてDPをしたときの最大値を出力
提出コード

void solve(){
    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    REP(i,n) cin >> a[i];
    vector<vector<ll>> dp(2, vector<ll>(n+10, -LINF));
    dp[1][0] = 0;
    REP(i,n){
        chmax(dp[0][i+1], dp[0][i]);
        chmax(dp[1][i+1], dp[1][i]);
        chmax(dp[0][i+1], dp[1][i] + a[i]);
        chmax(dp[1][i+1], dp[0][i] - a[i]);
    }
    ll ans = 0;
    REP(i,2) REP(j,n+1) chmax(ans, dp[i][j]);
    cout << ans << endl;
}

D. Rescue Nibel!

区間の左側と右側をvectorに入れて、ソートをする
これを昇順に見ていき、区間の左側なら個数を1個足す、右側なら個数を1個引くを繰り返す
区間の左側のときに、個数がK個以上なら今の個数をcntとすると _{cnt} C _kを加算する
ただし、すでに加算したものも重複して加算してしまうので
その前の状態 _{cnt-1} C _K引いてあげればいい
提出コード

void solve(){
    int n, k;
    cin >> n >> k;
    vector<pair<ll, int>> vp;
    REP(i,n){
        ll l, r;
        cin >> l >> r;
        vp.emplace_back(10*l, -1);
        vp.emplace_back(10*r+1, 1);
    }
    sort(vp.begin(), vp.end());
    ll cnt = 0;
    mint ans = 0;
    for(auto [t, c] : vp){
        // dumps(t, c);
        if(c == -1){
            cnt++;
            if(cnt >= k) ans += bc.com(cnt, k) - bc.com(cnt-1, k);
        }
        else cnt--;
    }
    cout << ans << endl;
}