接着剤の精進日記

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

Codeforces Round #629 (Div. 3)

codeforces.com

Dまで

A. Divisibility Problem

問題文

正の整数aとbが与えられる
一回の操作でaをa+1に変更できる
aがbで割り切れるようにするのに最小で何回操作が必要か

解法

aをbで割ったときの値を切り上げたものからaを引いたものが答え

提出コード

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int Q;
    cin >> Q;
    while(Q--){
        ll a, b;
        cin >> a >> b;
        if(a % b == 0) cout << 0 << endl;
        else{
            ll cnt = (a + b - 1) / b;
            cout << b * cnt - a << endl;
        }
    }
}

B. K-th Beautiful String

問題文

n-2個の'a'と2個の'b'からなる文字列がある
この文字列を並び替えて作れる文字列のうち、辞書順でK番目のものを出力せよ

解法

aaa...bbが最小で、 aaa...bab, aaabaab, ..., のように左側のbを跨ぐaの個数を考えると、aの数に応じて辞書順は1 + 2 + 3 + ...のように増えていく
なので等差数列の和を考えてKを超えない最大の整数を求めてあげて、後は差分で愚直にやればおっけー

提出コード

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int Q;
    cin >> Q;
    while(Q--){
        ll n, k;
        cin >> n >> k;
        ll cnt = 0;
        for(ll i = 1;i*(i+1)/2<k;i++){
            cnt = i;
        }
        k--;
        string ans = "";
        ans += string(n - 2 - cnt, 'a');
        k -= (cnt * (cnt + 1) / 2);
        ans += 'b';
        if(cnt - k > 0) ans += string(cnt - k, 'a');
        ans += 'b';
        if(k > 0) ans += string(k, 'a');
        cout << ans << endl;
    }
}

C. Ternary XOR

問題文

Ternary number であるxが与えられる
ternary XOR operation ⊙を2つのternary number aとbを用いて次のように定義する
𝑐=𝑎⊙𝑏 , 𝑐𝑖=(𝑎𝑖+𝑏𝑖)%3
この時、𝑎⊙𝑏 = x かつ max(a, b)が最小となるようなaとbを出力せよ

解法

先頭から見ていって'1'が出てきたかどうかで場合分け
'1'が初めて出てきたらaの方に'1'をつけてあげる
その後はbの方に数字を押し付けて上げていけば達成できる

提出コード

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int Q;
    cin >> Q;
    while(Q--){
        int n;
        string s;
        cin >> n >> s;
        string a = "", b = "";
        bool one = true;
        REP(i,n){
            if(s[i] == '2'){
                if(one){
                    a += '1';
                    b += '1';
                }
                else{
                    a += '0';
                    b += '2';
                }
            }
            else if(s[i] == '1'){
                if(one){
                    a += '1';
                    b += '0';
                    one = false;
                }
                else{
                    a += '0';
                    b += '1';
                }
            }
            else{
                a += '0';
                b += '0';
            }
        }
        cout << a << endl;
        cout << b << endl;
    }
}

D. Carousel

問題文

n個の動物の絵が環状に並んでいる
i番目の動物の絵の種類はt_iである
n個の絵に対し次の条件を満たすように色を塗っていく
・隣合う絵のうち、絵の種類が異なる場合、異なる色で塗る
この条件を満たすように色を塗っていく時、最小の色の数を出力し、その塗り方の一例を出力せよ

解法

本番で解けなかった
多くても3色で十分なのは良かったけど場合分けが上手く出来なかった
まず、絵の種類が1個なら1色で塗れる
nが偶数なら2色を交互に塗っていくことで達成できる
nが奇数のとき、同じ種類の絵が連続して並んでいる箇所があれば、そこを基準にnが偶数のときに帰着出来るので2色で塗れる
そうでなければ3色で塗る必要がある

提出コード

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int Q;
    cin >> Q;
    while(Q--){
        int n;
        cin >> n;
        vector<int> t(n);
        REP(i,n) cin >> t[i];
        bool monotone = true;
        REP(i,n-1) if(t[i] != t[i+1]) monotone = false;
        if(monotone){
            cout << 1 << endl;
            REP(i,n) cout << 1 << " ";
            cout << endl;
        }
        else{
            if(n % 2 == 0){
                cout << 2 << endl;
                REP(i,n) cout << (i % 2) + 1 << " ";
                cout << endl;
            }
            else{
                int same = -1;
                REP(i,n) if(t[i] == t[(i+1)%n]) same = i+1;
                if(~same){
                    cout << 2 << endl;
                    REP(i,same) cout << (i % 2) + 1 << " ";
                    for(int i=same;i<n;i++) cout << ((i + 1) % 2) + 1 << " " ;
                    cout << endl;
                }
                else{
                    cout << 3 << endl;
                    REP(i,n-1) cout << (i % 2) + 1 << " ";
                    cout << 3 << endl;
                }
            }
        }
    }
}

おわりに

Dギャグっぽい?ギャグが解けない
Eぱっと見た感じ良さそうな問題だから解いておきたい