接着剤の精進日記

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

トップ > Codeforces > Codeforces Round #702 (Div. 3)

Codeforces Round #702 (Div. 3)

Codeforces Codeforces Round #702 (Div. 3)

codeforces.com

A. Dense Array

$ 2 \times \min(a_i, a_{i+1}) \gt \max(a_i, a_{i+1}) $のとき、小さいほうから大きい方へ2倍ずつしていけばいいので2倍する必要のある回数の総和を求める
提出コード

void solve(){
    int n;
    cin >> n;
    vector<int> a(n);
    REP(i,n) cin >> a[i];
    int ans = 0;
    REP(i,n-1){
        if(max(a[i], a[i+1]) <= 2 * min(a[i], a[i+1])) continue;
        int cur = min(a[i], a[i+1]);
        while(2 * cur < max(a[i], a[i+1])){
            ans++;
            cur *= 2;
        }
    }
    cout << ans << endl;
}

B. Balanced Remainders

余ってるものから操作回数が少ない方に変えていく
提出コード

void solve(){
    int n;
    cin >> n;
    vector<int> a(n);
    vector<int> cnt(3);
    REP(i,n){
        cin >> a[i];
        a[i] %= 3;
        cnt[a[i]]++;
    }
    int ans = 0;
    REP(i,n){
        if(cnt[a[i]] <= n / 3) continue;
        if(a[i] == 0){
            if(cnt[1] < n / 3){
                cnt[1]++;
                cnt[0]--;
                ans++;
            }
            else if(cnt[2] < n / 3){
                cnt[2]++;
                cnt[0]--;
                ans += 2;
            }
        }
        else if(a[i] == 1){
            if(cnt[2] < n / 3){
                cnt[2]++;
                cnt[1]--;
                ans++;
            }
            else if(cnt[0] < n / 3){
                cnt[0]++;
                cnt[1]--;
                ans += 2;
            }
        }
        else{
            if(cnt[0] < n / 3){
                cnt[0]++;
                cnt[2]--;
                ans++;
            }
            else if(cnt[1] < n / 3){
                cnt[1]++;
                cnt[2]--;
                ans += 2;
            }
        }
    }
    cout << ans << endl;
}

C. Sum of Cubes

片方を固定するともう片方も一意に決まるのでそれが正の整数になる3乗根を持つかどうかわかればいい
これは二分探索で求めることができるので片方を全探索してもう片方は二分探索で求めればいい
事前に列挙しておけば二分探索いらなかった
提出コード

void solve(){
    ll x;
    cin >> x;
    for(ll a=1;a*a*a<=x;a++){
        ll b = x - a*a*a;
        if(b <= 0) continue;
        ll l = 1, r = 1e4;
        while(r - l > 1){
            ll m = (l + r) >> 1;
            if(m * m * m > b) r = m;
            else l = m;
        }
        if(l * l * l == b){
            cout << "YES" << endl;
            return;
        }
    }
    cout << "NO" << endl;
}

D. Permutation Transformation

再帰関数で操作を実際に行えばいい
提出コード

void solve(){
    int n;
    cin >> n;
    vector<int> a(n);
    REP(i,n) cin >> a[i];
    vector<int> dep(n, -1);
    auto dfs = [&](auto && self, int l, int r, int d) -> void{
        // dumps(l, r);
        if(l == r){
            dep[l] = d;
            return;
        }
        int ma = 0;
        int idx = 0;
        for(int i=l;i<=r;i++) if(chmax(ma, a[i])) idx = i;
        dep[idx] = d;
        if(l <= idx-1) self(self, l, idx-1, d+1);
        if(idx+1 <= r) self(self, idx+1, r, d+1);
    };
    dfs(dfs, 0, n-1, 0);
    REP(i,n) cout << dep[i] << " ";
    cout << endl;
}

E. Accidental Victory

昇順にソートをして考える
$ [0, i) $ が $ i $ に勝てるかどうかは $ \sum_{j=0} ^{i-1} a_j \geq a_i $ を満たしていればいい
よって上記を満たす区間 $ [l, n] $ を求めればいい
提出コード

void solve(){
    int n;
    cin >> n;
    vector<ll> a(n);
    REP(i,n) cin >> a[i];
    vector<int> ans, idx(n);
    iota(idx.begin(), idx.end(), 0);
    sort(idx.begin(), idx.end(), [&](int x, int y){
        return a[x] < a[y];
    });
    ll sum = 0;
    int l = 0;
    REP(i,n){
        // dumps(i, a[idx[i]], sum);
        if(sum < a[idx[i]]) l = i;
        sum += a[idx[i]];
    }
    for(int i=l;i<n;i++) ans.emplace_back(idx[i]);
    sort(ans.begin(), ans.end());
    cout << ans.size() << endl;
    for(auto x : ans) cout << x+1 << " ";
    cout << endl;
}

F. Equalize the Array

$ C $ を全探索する
各要素が何回出現するかをカウントし、各要素ごとに何個存在するかをカウントする
$ C $ を固定したときに必要になる操作回数は累積和を使うと $ \mathcal{O}(1) $ で求められる
提出コード

void solve(){
    int n;
    cin >> n;
    vector<int> a(n);
    map<int, int> mp;
    REP(i,n){
        cin >> a[i];
        mp[a[i]]++;
    }
    vector<int> cnt(n+2);
    for(auto [k, v] : mp) cnt[v]++;
    vector<ll> cum(n+2);
    REP(i,n+1) cum[i+1] = cum[i] + cnt[i];
    int ans = n;
    ll pre = 0;
    REP(i,n+1){
        int tmp = pre;
        if(cnt[i] == 0) continue;
        if(i+1 <= n) tmp += (n - pre - i * cnt[i]) - i * (cum[n+1] - cum[i+1]);
        pre += i * cnt[i];
        chmin(ans, tmp);
    }
    cout << ans << endl;
}

G. Old Floppy Drive

頭壊れた
一周するたびにどれだけ値が増減するかと一周するときに左からの累積maxを求めておく
$ x $ を超えないように何周するかは割り算で求めることができるので、残り1周を実際にシミュレートをすればいい
愚直にシミュレートすると $ \mathcal{O}(nm) $ かかるので累積maxを使って二分探索で求めればいい
1周だと境界でバグらせそうな気がしたので2周させた
提出コード

void solve(){
    int n, m;
    cin >> n >> m;
    vector<ll> a(n), x(m);
    REP(i,n) cin >> a[i];
    REP(i,m) cin >> x[i];
    ll cycle = 0;
    ll ma = -LINF;
    REP(i,n){
        cycle += a[i];
        chmax(ma, cycle);
    }
    vector<ll> cum(n, -LINF);
    cum[0] = a[0];
    ll sum = a[0];
    for(int i=1;i<n;i++){
        sum += a[i];
        chmax(cum[i], max(cum[i-1], sum));
    }
    REP(i,m){
        if(x[i] <= a[0]) cout << "0 ";
        else if(ma <= 0 or (ma < x[i] and cycle <= 0)) cout << "-1 ";
        else{
            ll cnt = 0;
            if(cycle > 0) cnt += floor_div(x[i] - ma - 1, cycle);
            if(cnt < 0) cnt = 0;
            ll cur = cnt * cycle;
            ll ans = -1;
            if(cnt == 1) ans += n;
            else if(cnt > 1) ans += n + (cnt - 1) * n;
            bool ok = false;
            {
                auto itr = lower_bound(cum.begin(), cum.end(), x[i] - cur);
                if(itr == cum.end()){
                    ok = true;
                    cur += cycle;
                    ans += n;
                }
                else{
                    cur += *itr;
                    ans += itr - cum.begin() + 1;
                }
            }
            if(ok){
                auto itr = lower_bound(cum.begin(), cum.end(), x[i] - cur);
                ans += itr - cum.begin() + 1;
            }
            cout << ans << " ";
        }
    }
    cout << endl;
}