接着剤の精進日記

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

Codeforces Round #635 (Div. 2)

codeforces.com

A. Ichihime and Triangle

問題文

正の整数a, b, c, dが与えられる
次の条件を満たす正の整数x, y, zのうち、三角形となるような3つ組を出力せよ

解法

難しすぎる
三角不等式を考えるとb, c, cなどを出力すればいい
提出コード

void solve(){
    ll a, b, c, d;
    cin >> a >> b >> c >> d;
    cout << b << " " << c << " " << c << endl;
}

B. Kana and Dragon Quest game

問題文

正の整数x, n, mが与えられる
以下の2つの操作が行える
1. h\lfloor \frac{h}{2} \rfloor + 10にする
2. hh - 10にする
1の操作を最大n回まで、2の操作を最大m回まで行える時hを0以下に出来るかどうかを判定せよ

解法

hが20以上の時、1の操作を行っても意味がなく、10未満だとむしろ悪くなる
そのためhが20以上の時に1の操作を行い、その後2の操作を行って0以下に出来るかを判定する
提出コード

void solve(){
    int x, n, m;
    cin >> x >> n >> m;
    while(n > 0 && x >= 20){
        x /= 2;
        x += 10;
        n--;
    }
    if(x <= 10 * m) cout << "YES" << endl;
    else cout << "NO" << endl;
}

C. Two Teams Composing

問題文

n頂点からなる木が与えられる
n頂点のうち、k個の頂点を選ぶことを考える
この時、選んだ頂点から頂点1までのパスのうち、選んだk個の頂点以外の頂点の総和を最大化したい
この最大値を答えよ

解法

葉から見ていくことを考える
この時、頂点までの距離が加算される
全ての葉が埋まった状態で、次に頂点を追加する時、その頂点は葉からのパスに含まれるため、子のサイズ分引いてあげる必要がある
そのため、予め各頂点の部分木の大きさをとその深さを求めておき、その差分が大きい順に取っていけばいい
本番では葉からbfsしたけど最初にpriority_queueに入れて大丈夫そう
提出コード

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, k;
    cin >> n >> k;
    sz.resize(n);
    G.resize(n);
    vector<int> deg(n);
    REP(i,n-1){
        int u, v;
        cin >> u >> v;
        --u, --v;
        G[u].push_back(v);
        G[v].push_back(u);
        deg[v]++, deg[u]++;
    }
    LCA<vector<vector<int>>> lca(G);
    lca.build();
    priority_queue<tuple<int,int,int>> pq;
    ll ans = 0;
    dfs(0, -1);
    // REP(i,n) cout << sz[i] << " ";
    // cout << endl;
    vector<bool> used(n);
    for(int i=1;i<n;i++) if(deg[i] == 1) pq.emplace(lca.dist(0,i)-(sz[i] - 1), i, -1);
    while(k > 0 && !pq.empty()){
        auto [dist, cur, par] = pq.top(); pq.pop();
        if(used[cur]) continue;
        ans += dist;
        k--;
        used[cur] = true;
        for(auto nv : G[cur]){
            if(nv == par) continue;
            pq.emplace(lca.dist(0, nv)-(sz[nv] - 1), nv, cur);
        }
    }
    cout << endl;
    cout << ans << endl;
}

D. Xenia and Colorful Gems

問題文

赤、緑、青のgemがそれぞれ n_r, n_g, n_b個あり、それぞれの重さはr_i, g_i, b_iである
各gemを一つずつ選び次の式を最小化することを考える
 (x - y) ^ 2 + (y - z) ^ 2 + (z - x) ^ 2
この時、得られる値のうち最小のものを出力せよ

解法

こういうのはとりあえず1個固定することを考える
その後、式を見ると最小化にするためにはx = y = zに近づける必要があるのでlower_boundなどで探索すればいい
本番では赤を固定して、左右を探索してたんだけど、これだけだと不足っぽい
よく考えると3色の並べ方は3!しかないので全部のパターンを試せばいい
提出コード

void solve(){
    int nr, ng, nb;
    cin >> nr >> ng >> nb;
    vector<ll> R(nr), G(ng), B(nb);
    REP(i,nr) cin >> R[i];
    REP(i,ng) cin >> G[i];
    REP(i,nb) cin >> B[i];
    sort(R.begin(), R.end());
    sort(G.begin(), G.end());
    sort(B.begin(), B.end());
    ll ans = 3 * LINF;
    auto f = [&](ll a, vector<ll> &b, vector<ll> & c) -> void{
        auto itr1 = upper_bound(b.begin(), b.end(), a);
        auto itr2 = lower_bound(c.begin(), c.end(), a);
        if(itr1 == b.begin() || itr2 == c.end()) return;
        itr1--;
        ll tmp = (a - *itr1) * (a - *itr1) + (a - *itr2) * (a - *itr2) + (*itr1 - *itr2) * (*itr1 - *itr2);
        chmin(ans, tmp);
    };
    
    REP(i,nr){
        f(R[i], G, B);
        f(R[i], B, G);
    }
    REP(i,ng){
        f(G[i], R, B);
        f(G[i], B, R);
    }
    REP(i,nb){
        f(B[i], R, G);
        f(B[i], G, R);
    }
    cout << ans << endl;
}

おわりに

最近のdiv2 Aほんとむずかしい