接着剤の精進日記

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

Codeforces Round #640 (Div. 4)

codeforces.com

緑以下Ratedのdiv4
全完出来たけど前半割と難しくない?後半はdiv3より流石に簡単だったけど(というかdiv3の後ろ難しすぎる)

A. Sum of Round Numbers

問題文

正の整数nが与えられる
nを先頭桁以外が0の整数の和で表現する
そのような整数の最小の数とそのそれぞれの整数を出力せよ

解法

下の桁から見ていき、その桁が0以外なら桁数分掛けたものを答えに加える
提出コード

void solve(){
    int n;
    cin >> n;
    vector<int> ans;
    int cur = 1;
    while(n > 0){
        int d = n % 10;
        if(d > 0) ans.emplace_back(d * cur);
        cur *= 10;
        n /= 10;
    }
    cout << ans.size() << endl;
    for(auto x : ans) cout << x << " ";
    cout << endl;
}

B. Same Parity Summands

問題文

正の整数nとkが与えられる
k個の0以上の整数からなる数列aの和がnとなるようなものを見つけたい
ただし、数列の要素の偶奇は全て一致していなければならない
このような数列が存在する時、その一つを出力せよ

解法

頭壊れた
nが奇数、kが偶数のときは絶対作れない
nが奇数、kが奇数のときはn \geq kなら必ず作れる
nが偶数、kが偶数のときはn \geq 2kなら必ず作れる
nが偶数、kが奇数のときはn \geq kなら必ず作れる
作れるときは一番小さい要素を出力して、最後の一つで帳尻を合わせればいい
提出コード

void solve(){
    int n, k;
    cin >> n >> k;
    if(n == k){
        cout << "YES" << endl;
        REP(i,k) cout << 1 << " ";
        cout << endl;
        return;
    }
    if(n < k){
        cout << "NO" << endl;
        return;
    }

    if(n & 1){
        if(k & 1){
            if(n >= k){
                cout << "YES" << endl;
                REP(i,k-1) cout << 1 << " ";
                cout << n - (k - 1) << endl;
            }
            else cout << "NO" << endl;
        }
        else cout << "NO" << endl;
    }
    else{
        if(k & 1){
            if(n >= 2 * k){
                cout << "YES" << endl;
                REP(i,k-1) cout << 2 << " ";
                cout << n - 2 * (k - 1) << endl;
            }
            else cout << "NO" << endl;
        }
        else{
            if(n >= k){
                cout << "YES" << endl;
                REP(i,k-1) cout << 1 << " ";
                cout << n - (k - 1) << endl;
            }
            else cout << "NO" << endl;
        }
    }
}

C. K-th Not Divisible by n

問題文

正の整数nとkが与えられる
nの倍数でないもののうち、k番目の整数を出力せよ

解法

にぶたんでもできそうだけど算数したほうが早そうなので算数をした
まず、 \lfloor \frac{k}{n - 1} \rfloor番目のnの倍数以下の整数は全て使うことになる
この時、nの倍数でないものの個数は \lfloor \frac{k}{n - 1} \rfloor \times (n - 1)個となる
そのため、残っている個数は(n -1)個以下なので、 \lfloor \frac{k}{n - 1} \rfloor \times nからその分を足していく
ただし、残りが0個のときはその分引いて上げる必要がある
提出コード

void solve(){
    ll n, k;
    cin >> n >> k;
    ll cur = k / (n - 1) * n;
    k -= k / (n - 1) * (n - 1);
    REP(i,k) cur++;
    if(k % (n-1) == 0) cur--;
    cout << cur << endl;
}

D. Alice, Bob and Candies

問題文

n個のキャンディがありそのサイズはa_iである
Aliceはこのキャンディーを左から、Bobは右から食べていく
この時、1ターンで食べるキャンディのサイズの合計は、その前のターンより心に大きくなるまで食べなければならず、大きくなった瞬間食べるのをやめる
Aliceから最初のターンを始める時、終わるまでにかかるターン数、Aliceが食べたキャンディのサイズの合計、Bobが食べたキャンディのサイズの合計を出力せよ

解法

実際にシミュレートしていけばいい

提出コード

void solve(){
    int n;
    cin >> n;
    vector<int> a(n);
    REP(i,n) cin >> a[i];
    int cur = 0;
    int l = 0, r = n - 1;
    int turn = 0;
    int Alice = 0, Bob = 0;
    while(l <= r){
        int tmp = 0;
        if(turn & 1){
            while(tmp <= cur && l <= r){
                tmp += a[r];
                r--;
            }
            Bob += tmp;
        }
        else{
            while(tmp <= cur && l <= r){
                tmp += a[l];
                l++;
            }
            Alice += tmp;
        }
        cur = tmp;
        turn++;
    }
    cout << turn << " " << Alice << " " << Bob << endl;
}

E. Special Elements

問題文

n個の正の整数からなる数列aが与えられる
a_i = a_l + a_{l+1} + ... + a_r ( 1 \leq l \lt r \leq n)を満たすペア(l, r)が存在する時、a_iをspecialと呼ぶ
与えられた数列aのうち、specialなものの個数を出力せよ

解法

全探索しても十分に間に合うので区間の和を全探索する
メモリの制約が小さいのでしゃくとりっぽくやった
提出コード

void solve(){
    int n;
    cin >> n;
    vector<int> a(n);
    map<int, int> mp;
    REP(i,n){
        cin >> a[i];
        mp[a[i]]++;
    }
    int ans = 0;
    for(int i=2;i<n;i++){
        int sum = 0;
        REP(j,i) sum += a[j];
        if(mp.count(sum)){
            ans += mp[sum];
            mp.erase(sum);
        }
        for(int j=i;j<n;j++){
            sum -= a[j-i];
            sum += a[j];
            if(mp.count(sum)){
                ans += mp[sum];
                mp.erase(sum);
            }
        }
    }
    cout << ans << endl;
}

F. Binary String Reconstruction

問題文

'0'と'1'からなる"binary string" sがある
sのうち、長さが2の連続部分文字列を考える
この連続部分文字列のうち、'1'が出現する個数が0、1、2個のものの個数をそれぞれn0、n1、n2とする
n0、n1、n2が与えられるのでこれを満たすような文字列 sを出力せよ
これを満たす文字列は必ず存在することが保証される

解法

初めにn0の分だけ"00...0"を作る
今作ったものに"1010..."のように作ったものをくっつける
この時偶数分だけ後ろにつけて、奇数分があれば先頭に1個くっつけると楽
後は先頭か後ろが'1'になっているのでn2分だけ"111..."をくっつける 提出コード

void solve(){
    int n0, n1, n2;
    cin >> n0 >> n1 >> n2;
    string ans = "";
    if(n0 > 0) ans = string(n0+1, '0');
    if(n1 > 0){
        if(ans == "") ans = '0';
        if(n1 % 2 == 0){
            REP(i,n1-1){
                if(i & 1) ans += '0';
                else ans += '1';
            }
            ans = "1" + ans;
        }
        else{
            REP(i,n1){
                if(i & 1) ans += '0';
                else ans += '1';
            }
        }
    }
    if(ans == "") ans = string(n2+1, '1');
    else if(ans[0] == '1') ans = string(n2, '1') + ans;
    else if(ans.back() == '1') ans += string(n2, '1');
    cout << ans << endl;
}

G. Special Permutation

問題文

正の整数nが与えられる
1 からnまでの順列pを考える
この時、1 \leq i \lt nに対して、 2 \leq |p_i - p_{i+1} | \leq 4を満たすような順列pを求めたい
このような順列が存在する時、そのような順列を一つ出力せよ

解法

実は、 n \geq 4のとき ... 7, 5, 3, 1, 4, 2, 4, 6, 8, ... のように[3, 1, 4, 2]の左側に奇数、右側に偶数を並べていくことでそのような順列を作ることが出来る
残り時間が少なかったのもあってコンテスト中は全探索通りそうだなーって思ったので全探索を書いて投げた
間に合いそうだなーって思ったけどちゃんと見積もれてたわけじゃないので、こどふぉだとあんまりやらないほうがいいね
提出コード

void solve(){
    int n;
    cin >> n;
    if(n <= 2){
        cout << -1 << endl;
        return;
    }
    vector<vector<int>> G(n+10);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(i == j) continue;
            if(2 <= abs(i - j) &&  abs(i - j) <= 4) G[i].emplace_back(j);
        }
    }
    vector<int> ans;
    vector<bool> used(n + 10);
    auto dfs = [&](auto && self, int cur, int par, int cnt) -> bool{
        used[cur] = true;
        if(cnt == n){
            ans.push_back(cur);
            return true;
        }
        for(auto nv : G[cur]){
            if(nv == par) continue;
            if(used[nv]) continue;
            if(self(self, nv, cur, cnt + 1)){
                ans.push_back(cur);
                return true;
            }
        }
        used[cur] = false;
        return false;
    };

    dfs(dfs, 2, -1, 1);
    if(ans.size() < n){
        cout << -1 << endl;
        return;
    }
    for(auto x : ans) cout << x << " ";
    cout << endl;
}

おわりに

div4楽しい
序盤結構辛く感じたけどrated帯の人どうなんだろうね