接着剤の精進日記

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

Codeforces Round #628 (Div. 2)

codeforces.com

需要あるのかわからないけどこどふぉも書いていくことにした
簡単に訳した問題文も載せるつもりなので英語に拒否感ある人にもやってほしいなあ
訳とか結構雰囲気でやっているので間違っているところとかあればぜひ指摘してください

Problem - A - Codeforces

問題文

ある整数xが与えられる
 GCD(a, b) + LCM(a, b) = xを満たす(a,b)の組をどれか1つ出力せよ

解法

これはギャグ…
a = 1とすると、GCD(a, b)は必ず1になり
LCM(a, b)は必ずbになるので a = 1, b = x - 1とすればいい

提出コード

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int Q;
    cin >> Q;
    while(Q--){
        ll x;
        cin >> x;
        cout << 1 << " " << x - 1 << endl;
    }
}

Problem - B - Codeforces

問題文

長さnの数列aが与えられる
元の数列をa = [3, 2, 1]とすると、任意の回数aを後ろに付け加えて、新しく数列を作ることが出来る
ex) [3, 2, 1, 3, 2, 1, 3, 2, 1, ...]
任意の回数この操作を行ったときに作ることが出来る数列のうち、狭義単調増加列となる長さの最大を求めよ

解法

任意の回数操作を行っても、元の数列aに含まれる要素以外は出現しないことがわかる
そのため、任意の回数を行っても作れる狭義単調増加列の最大はaに含まれる要素数(重複は除く)になることがわかる
また、連続しない部分列でもいいため、任意の回数操作を行えば、この最大の長さの狭義単調増加列を作ることが出来る
よって、setなどで重複を省いたaの要素数を求めてあげればいい
提出コード

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int Q;
    cin >> Q;
    while(Q--){
        int n;
        cin >> n;
        set<int> st;
        REP(i,n){
            int a;
            cin >> a;
            st.insert(a);
        }
        cout << st.size() << endl;
    }
}

Problem - C - Codeforces

問題文

n頂点の木が与えられる
以下の条件を満たすように各辺にラベルを付けたものを出力せよ

  1. ラベルの値は0 ~ n-2まで
  2. 各辺のラベルはそれぞれ異なる
  3. 「全てのペア(u, v) に対するMEX(u, v)の最大値」が最小となる

MEX(u, v)は、uからvまでの最短経路上に含まれないラベルの中で、最小のラベルの値

解法

これ難しいけどギャグらしい
本番中は全然気づけなかった
まず、次数が3以上になるノードを見つける
そのノードから出ている辺に0, 1, 2, ...と番号を振っていく
それ以外の辺は余っているラベルを振っていくといい

提出コード

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    vector<vector<int>> G(n);
    vector<int> ans(n, -1);
 
    REP(i,n-1){
        int u, v;
        cin >> u >> v;
        --u, --v;
        G[u].push_back(i);
        G[v].push_back(i);
    }
 
    int cur = 0;
    REP(v,n){
        if((int)G[v].size() < 3) continue;
        for(auto e : G[v]) if(ans[e] == -1) ans[e] = cur++;
    }
    REP(e,n) if(ans[e] == -1) ans[e] = cur++;
 
    REP(i,n-1) cout << ans[i] << endl;
}

Problem - D - Codeforces

問題文

整数uとvが与えられる
任意の整数を使い、そのxorの合計がu、総和がvとなるような要素のうち、要素の個数が最小ものを出力せよ

解法

これ難しかったけど本番で解けて嬉しい
まずu > vなら絶対作れない
v - uの偶奇が一致していなければこれも作れない
それ以外の場合、まず要素のxorの合計をuで固定したいのでuを取ると、残りの総和はv - uとなる
ここで、v - uの偶奇が一致しているとv - uの1bit目が0となるので(v -u) >> 1が出来る
そして、(v - u) >> 1を2つ要素として考えると、2 * (v - u) >> 1はv - u
(v - u) >> 1 xor (v - u) >> 1 = 0 となるので3つで必ず構築できるようになる
ただし、uと立っているbitが被っていなければ2つの要素で構築できるので注意
本番は3つで構築出来るとか気づいていなくて、上位bitから貪欲に割り当てていく脳筋コードで通した()
提出コード

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll u, v;
    cin >> u >> v;
    if(u % 2 != v % 2){
        cout << -1 << endl;
        return 0;
    }
    if(u > v){
        cout << -1 << endl;
        return 0;
    }
    vector<ll> ans;
    v -= u;
    ans.push_back(u);
    if(v != 0){
        for(int i=60;i>=0;i--){
            if(v >> i & 1){
                int cnt = 2;
                ll t = 1LL << (i - 1);
                for(auto &x : ans){
                    //cout << t << " " << x << endl;
                    if(x >> (i - 1) & 1) continue;
                    x ^= t;
                    cnt--;
                    if(cnt <= 0) break;
                }
                REP(j, cnt) ans.push_back(t);
            }
        }
    }
    else{
        if(ans[0] == 0) cout << 0 << endl;
        else{
            cout << ans.size() << endl;
            for(auto x : ans) cout << x << " ";
            cout << endl;
        }
        return 0;
    }
    cout << ans.size() << endl;
    for(auto x : ans) cout << x << " ";
    cout << endl;
}

おわりに

これの前にあったAtCoderで冷えたけどレート合計プラマイゼロなのでよし!w
これからこどふぉも書いていこうと思うけど英語でこどふぉやらないでいる人たちがやり始めてくれると嬉しいな
訳した問題文読んで問題通すだけでもいいので