接着剤の精進日記

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

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

Codeforces Round #636 (Div. 3)

Codeforces Codeforces Round #636 (Div. 3)

codeforces.com

A. Candies

問題文

n個のキャンディがある
Vovaは1日目にx個、2日目に2x個、3日目に4x個…とキャンディを買いました
この時 x + 2x + 4x + ... + 2^{k-1}x = nを満たすxを出力せよ
ただし、kは k \gt 1を満たす

解法

左辺が 2^{k} - 1なのでkは最大でも30程度なので全探索すればいい
提出コード

void solve(){
    ll n;
    cin >> n;
    ll cnt = 3;
    ll base = 2;
    while(cnt <= INF){
        if(n % cnt == 0){
            cout << n / cnt << endl;
            return;
        }
        base *= 2;
        cnt += base;
    }
}

B. Balanced Array

問題文

2で割り切れる正の整数nが与えられる
以下の条件を満たすような数列を構築したい
1. 最初の\frac{n}{2}個の要素は2で割り切れる
2. 2つ目の\frac{n}{2}個の要素は2で割り切れない
3. 全ての要素は正で、全て異なる値
4. 最初の\frac{n}{2}の要素の合計と2つ目の\frac{n}{2}個の要素の合計は等しい
このような数列が構築可能ならばその一つを出力せよ

解法

\frac{n}{2}が奇数ならば、構築できない
偶数ならば必ず構築できるので、偶数は適当に
奇数は最後の1要素で合計が等しくなるように調整すればいい
提出コード

void solve(){
    int n;
    cin >> n; // n is even
    if((n / 2) % 2 == 1){
        cout << "NO" << endl;
        return;
    }
    vector<int> even, odd;
    ll sum = 0;
    for(int i=2;i<=n;i+=2){
        even.push_back(i);
        sum += i;
    }
    for(int i=1;i<n-2;i+=2){
        odd.push_back(i);
        sum -= i;
    }
    odd.push_back(sum);
    cout << "YES" << endl;
    for(auto x : even) cout << x << " ";
    for(auto x : odd) cout << x << " ";
    cout << endl;
}

C. Alternating Subsequence

問題文

長さがnの数列aが与えられる
その部分列を考えたときに、隣り合う要素の符号が異なるものを考える
この時、その部分列の長さが最大となるように部分列を構築する時、その総和が最大を出力せよ

解法

符号ごとにランレングス圧縮のような感じで圧縮する
符号が同じ場合はその要素のmaxを保存し、符号が変わったらmaxを部分列に追加し、同様に続けていく
提出コード

void solve(){
    int n;
    cin >> n;
    vector<ll> a(n);
    REP(i,n) cin >> a[i];
    vector<ll> res;
    ll cur = a[0];
    for(int i=1;i<n;i++){
        if(cur * a[i] < 0){
            res.push_back(cur);
            cur = a[i];
        }
        else chmax(cur, a[i]);
    }
    res.push_back(cur);
    int sz = size(res);
    
    ll ans = 0;
    REP(i,sz) ans += res[i];
    if(sz == 0) ans = -1;
    cout << ans << endl;
}

D. Constant Palindrome Sum

問題文

n個の整数からなる数列が与えられる
任意の回数、a_iを [1;k]に置き換える操作が行える
以下の条件を満たすように操作を行った時、操作回数の最小を答えよ
1. 全てのa_iはk以下を満たす
2. 1 \leq i \leq \frac{n}{2}に対し、 a_i + a_{n-i+1} = xを満たす

解法

\frac{n}{2}個のペアごとに何回の操作でどの範囲の区間の値に変更できるかを考える
そうするとimos法が使えることがわかるので
最大2回まで操作を行えば十分なので、1回の操作で作れる区間と2回の操作で作れる区間をimos法で前計算をする
その後、xをどの値にするかを全探索すればいい

提出コード

void solve(){
    int n, k;
    scanf("%d %d", &n, &k);
    vector<int> a(n), imos(2*k+10);
    REP(i,n) scanf("%d", &a[i]);
 
    REP(i,n/2){
        int x = a[i], y = a[n-i-1];
        if(x > y) swap(x, y);
        int sum = x + y;
        int lt = sum - (y - 1);
        int ut = sum + (k - x);
        imos[lt]++, imos[sum]--;
        imos[sum+1]++, imos[ut+1]--;
        if(lt != 2) imos[2] += 2, imos[lt] -= 2;
        if(ut != 2 * k) imos[ut+1] += 2, imos[2*k+1] -= 2;
    }
    REP(i,2*k) imos[i+1] += imos[i];
    int ans = INF;
    for(int i=2;i<=2*k;i++) chmin(ans, imos[i]);
    cout << ans << '\n';
}

E. Weights Distributing

問題文

n個の頂点とm個の辺からなる無向グラフとm個の重みpが与えられる
頂点aから頂点bに行き、その後頂点bから頂点cに移動することを考える
この時、通った辺の重みが最小となるように与えられたpを各辺に割り振っていく
このようにして達成できる重みの総和の最小値を答えよ

解法

aからb、bからcへ移動することを考えると中継点が存在することがわかる
そのため、この中継点からの距離を最小となるようにすればいい
a,b,cからの最短距離をbfsなどで前計算しておく
後はpを昇順にソートし、累積和を取っておくと各中継点からの重みの総和を求めることが出来る
提出コード

void solve(){
    int n, m, a, b, c;
    cin >> n >> m >> a >> b >> c;
    --a, --b, --c;
    vector<int> p(m);
    vector<ll> cum(m+1);
    REP(i,m) cin >> p[i];
    sort(p.begin(), p.end());
    REP(i,m) cum[i+1] = cum[i] + p[i];
    
    vector<vector<int>> G(n);
    REP(i,m){
        int u, v;
        cin >> u >> v;
        --u, --v;
        G[u].emplace_back(v);
        G[v].emplace_back(u);
    }
    vector<int> da(n, INF), db(n, INF), dc(n,INF);
    da[a] = db[b] = dc[c] = 0;
    auto bfs = [&](int s, vector<int> &d) -> void{
        queue<int> q;
        q.push(s);
        while(!q.empty()){
            int cur = q.front();
            q.pop();
            for(auto nv : G[cur]){
                if(d[nv] != INF) continue;
                d[nv] = d[cur] + 1;
                q.push(nv);
            }
        }
    };
 
    bfs(a, da);
    bfs(b, db);
    bfs(c, dc);
 
    ll ans = LINF;
    REP(i,n){
        if(da[i] + db[i] + dc[i] > m) continue;
        chmin(ans, cum[db[i]] + cum[da[i] + db[i] + dc[i]]);
    }
    cout << ans << endl;
}

おわりに

中継点を全探索するのは第一回のPASTにあったね、忘れてた