Codeforces Round #657 (Div. 2) 参加記

A Acacius and String

なら、毎回ある一箇所を変更して一個だけかどうかを判定すればよいです。は難しそうです。

Div2-Aにしては実装が重いですね。

void solve(){
    int N;
    string S;
    cin >> N >> S;
    string t = "abacaba";
    vector<int> idxes;
    rep(i,N-6){
        string tmp = S.substr(i,7);
        if(tmp == t)continue;
        bool ok = true;
        rep(i,7){
            if(tmp[i] == '?')continue;
            if(tmp[i] != t[i])ok = false;
        }
        if(ok){
            idxes.push_back(i);
        }
    }
    auto f = [&](string T) -> int{
        int sz = T.size();
        int res = 0;
        rep(i,sz-6){
            string tmp = T.substr(i, 7);
            if(tmp == t)res++;
        }
        return res;
    };
    int cnt = f(S);
    if(cnt == 0){
        //変えないといけない
        int start = -1;
        for(auto p: idxes){
            string T = S;
            rep(j,7){
                T[p+j] = t[j];
            }
            int cntt = f(T);
            if(cntt == 1){
                start = p;
                break;
            }
        }
        if(start == -1){
            cout << "No" << endl;
        }
        else{
            cout << "Yes" << endl;
            rep(j,7){
                S[start+j] = t[j];
            }
            rep(i,N){
                if(S[i] == '?')cout << 'd';
                else cout << S[i];
            }
            cout << endl;
        }
    }
    else if(cnt == 1){
        cout << "Yes" << endl;
        rep(i,N){
            if(S[i] == '?')cout << 'd';
            else cout << S[i];
        }
        cout << endl;
    }
    else{
        cout << "No" << endl;
    }
}

B Dubious Cyrpto

「が与えられるので、なる整数で、を満たすものを求めよ。」という問題。

を固定して、の倍数をに近づけて、その余りをの差で表現できるかを判定する。

void solve(){
    ll l, r, m;
    cin >> l >> r >> m;
    for(ll a = l; a <= r; a++){
        if(m >= a){
            ll d = m % a;
            // b > cで幅d持てるかどうか
            if(l + d <= r){
                cout << a << " " << l+d << " " << l << endl;
                return;
            }
            d = ((m+a-1)/a)*a - m;
            if(l + d <= r){
                cout << a << " " << l << " " << l + d << endl;
                return;
            }
        }
        else{
            ll d = a - m;
            // c > bで幅d持てるかどうか
            if(l + d <= r){
                cout << a << " " << l << " " << l+d << endl;
                return;
            }
        }
    }
}

C Choosing flowers

複数取る花は高々個です。よって、それを全探索します。取る花のをとすると、のは全て取ることになります。を大きい順に固定していくことで、尺取り法で実装できます。 が小さくなっていくとの候補が増えていくからです。

ある花を取るとしたとき、必ずも取らないといけません。これは、尺取りで進めているの範囲に入ってない場合は追加します。

また、コーナーケースとして、複数取る花が個の場合があります。

void solve(){
    ll N, M;
    cin >> N >> M;
    vector<ll> a(M), b(M);
    vector<l_l> v;
    rep(i,M){
        cin >> a[i] >> b[i];
        v.emplace_back(b[i], a[i]);
    }
    // aの大きい順に並んでいる
    sort(all(a), greater<>());
    sort(all(v), greater<>());
    ll ans = 0;
    // baseライン
    if(N <= M)rep(i,N)ans += a[i];
    ll sum = 0;
    int idx = 0;//尺取りのindex
    // iのbで残り全部埋めて、b[i] < a[i]花は取る
    rep(i,M){
        // b < aを取る
        ll bb = v[i].first;
        while(idx < M && bb < a[idx]){
            sum += a[idx];
            idx++;
        }
        ll cnt = idx; // 追加個数
        ll tmp = sum;
        ll aa = v[i].second;
        // 尺取りで入っていないので足す
        if(aa <= bb){
            tmp += aa;
            cnt++;
        }
        // 残りは全てbb
        if(N - cnt < 0)continue;
        tmp += (N - cnt) * bb;
        chmax(ans, tmp);
    }
    cout << ans << endl;
}