Codeforces Round #653 (Div. 3)

codeforces.com

A. Required Remainder

kはxの倍数にyだけ足したものと考えていいので
nを超えない範囲のxの倍数を求めてからyを足す
提出コード

void solve(){
    ll x, y, n;
    cin >> x >> y >> n;
    ll k = n / x * x;
    if(k + y <= n) cout << k + y << endl;
    else cout << k - x + y << endl;
}

B. Multiply by 2, divide by 6

まず3で割り切れないときは答えは-1になる
また、2と3以外の素因数が含まれる場合も-1になる
nを3で割れる回数をthree, 2で割れる回数をtwoとする
操作は素因数2を増やすか6で割るかなのでなら不可能
それ以外の場合となる
提出コード

void solve(){
    int n;
    cin >> n;
    if(n == 1){
        cout << 0 << endl;
        return;
    }
    if(n % 3){
        cout << -1 << endl;
        return;
    }
    int tmp = n;
    int three = 0;
    while(tmp % 3 == 0) three++, tmp /= 3;
    int two = 0;
    while(tmp % 2 == 0) two++, tmp /= 2;
    if(tmp > 1){
        cout << -1 << endl;
        return;
    }
    if(two > three){
        cout << -1 << endl;
        return;
    }
    int ans = min(two, three);
    three -= ans;
    ans += 2 * three;
    cout << ans << endl;
}

C. Move Brackets

操作をする前に'(' と ')'が並んでいるものは取ってしまっていい
これはstackなどでシミュレートする
次に残ったものに対し操作を行い'('と')'のペアを作る
この時、1回の操作でペアを作ることが出来るので
シミュレートして残った文字列の長さを2で割ったものが答え
提出コード

void solve(){
    int n;
    string s;
    cin >> n >> s;
    vector<char> st;
    REP(i,n){
        if(st.empty()) st.push_back(s[i]);
        else{
            if(st.back() == '(' && s[i] == ')') st.pop_back();
            else st.push_back(s[i]);
        }
    }
    cout << st.size() / 2 << endl;
}

D. Zero Remainder Array

操作を行い、最終的にxが幾つになるか考える
をmod k で考えると同じ余りの組はその個数分の周期が必要になる
そのため、各mod k の値ごとにxが最大で幾つになるかのmaxを求めてあげればいい
提出コード

void solve(){
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    map<ll, ll> mp;
    REP(i,n){
        cin >> a[i];
        a[i] %= k;
        mp[a[i]]++;
    }
    ll ans = 0;
    for(auto [x, y] : mp){
        if(x == 0) continue;
        // cout << k - x << " " << x << " " << y << endl;
        chmax(ans, k*(y-1) + k-x + 1);
    }
    cout << ans << endl;
}

E1. Reading Books (easy version)

この間のABC-Cと同じような感じ
AliceとBobが本を個共有する時、残りの個はの小さい順に読むのが最適となる
AliceとBob、また共有する本をそれぞれ配列に入れ、昇順にソートした後
AliceとBobの配列の累積和を取っておき、共有する本の数を全探索すればいい
提出コード

void solve(){
    int n, k;
    cin >> n >> k;
    vector<int> alice, bob, both;
    REP(i,n){
        int t, a, b;
        cin >> t >> a >> b;
        if(a & b) both.emplace_back(t);
        else if(a) alice.emplace_back(t);
        else if(b) bob.emplace_back(t);
    }
    sort(alice.begin(), alice.end());
    sort(bob.begin(), bob.end());
    sort(both.begin(), both.end());

    int a = alice.size(), b = bob.size(), c = both.size();
    vector<ll> cum_a(a+1), cum_b(b+1);
    for(int i=0;i<a;i++){
        cum_a[i+1] = cum_a[i] + alice[i];
    }
    for(int i=0;i<b;i++){
        cum_b[i+1] = cum_b[i] + bob[i];
    }
    ll ans = LINF;
    ll sum = 0;
    REP(i,min(c, k)){
        sum += both[i];
        int rest = k - i - 1;
        if(rest > b || rest > a) continue;
        chmin(ans, sum + cum_a[rest] + cum_b[rest]);
    }
    if(k <= a && k <= b) chmin(ans, cum_a[k] + cum_b[k]);
    if(ans == LINF) ans = -1;
    cout << ans << endl;
}