スコルの知恵袋

主にプログラミング関係の気になったこと等をまとめたブログ

Codeforces Round #657 (Div. 2) 感想

競プロ日記 競プロ

問題

Dashboard - Codeforces Round #657 (Div. 2) - Codeforces

感想

2完。むっっっっっず！ 今回、writerの威圧感がすごかったから嫌な予感はしてたんだよな～～～。 でもCは解けるべき問題だった。くやしい。。。

レート変動は 1932 -> 1900 でギリギリ紫を守れた。いよいよ次回Div.1。たのしみ～～。

A - Acacius and String

3分で解いてやるぜ～～ｗｗと意気込んでいたら全然解けなくてめちゃくちゃ焦った。

最初、"exactly once" を読み飛ばしていて（太字を読み飛ばすな） 「"abacaba"にできるか前から確認すればいいだけやん楽勝！」と言いながら実装するものの、もちろんサンプルが合わず？？となった。

そして、問題文に "exactly once" と書いてあることを発見し、冷や汗をかく。

ここで、やべ～～と思いながらDashboardを見るとまだ200人くらいしかACしてなくてちょっと安心する。

しかし、そこから30分くらい迷走してしまい、絶望する。

結局、 s[ i..i+6 ] を "abacaba" にできるかを確認し、できるときに s 全体に "abacaba" が連続部分列として何回登場するかをカウントし、 それがちょうど 1 になるかを確かめるだけでよかった。"abacaba" にする部分以外の ? は適当に z とかで埋めとけばいい。

いつもに比べてあまりにも解かれていなかったため、変に難しく考えてしまった。反省。。。

提出コード

リンク： http://codeforces.com/contest/1379/submission/87307205

void solve() {
    int Q;
    cin >> Q;
    const string target = "abacaba";
    while (Q--) {
        ll N;
        cin >> N;
        string S;
        cin >> S;
 
        bool ok = false;
        for (ll i = 0; i < N; i++) {
            if (i + 7 > N) continue;
            string S_cpy = S;
            bool good = true;
            for (ll j = 0; j < 7; j++) {
                if (S_cpy[i + j] != '?' && S_cpy[i + j] != target[j]) {
                    good = false;
                    break;
                }
            }
            if (good) {
                for (ll j = 0; j < 7; j++) {
                    if (S_cpy[i + j] == '?') {
                        S_cpy[i + j] = target[j];
                    }
                }
 
                ll cnt = 0;
                for (ll j = 0; j < N; j++) {
                    if (j + 7 > N) continue;
                    bool fg = true;
                    for (ll k = 0; k < 7; k++) {
                        if (S_cpy[j + k] != target[k]) {
                            fg = false;
                            break;
                        }
                    }
                    if (fg) {
                        ++cnt;
                    }
                }
 
                if (cnt > 1) {
                    good = false;
                }
            }
 
            if (good) {
                ok = true;
                S = S_cpy;
                break;
            }
        }
 
        for (ll i = 0; i < N; i++) {
            if (S[i] == '?') {
                S[i] = 'z';
            }
        }
 
        if (ok) {
            cout << "Yes\n";
            cout << S << "\n";
        }
        else {
            cout << "No\n";
        }
    }
}

B - Dubious Cyrpto

Aでの失敗に動揺してしまい、Bでもあたふたして時間を消費してしまった。メンタルさん......

でも、この問題も Div.2-B にしてはむずかしいよね。

d = b -c とおくと、 m = na + d となるから m \equiv d \pmod a。また、 L - R \le d \le R - L。

a を固定して考える。

[L - R, R - L ] は 0 について対称な区間であることに注目すると、 r = m \bmod a\ (0 \le r \lt a) としたとき、 d の候補として考えるのは d = r または d = r - a のみでいいことが分かる（この2つのいずれかが最も0に近い）。

d を d = r または d = r - a と定めて L - R \le d \le R - L を満たすか確認し、満たされていれば d をその値で確定する。

ただし、 d = r とするときは確認すべき条件がもう一つあって、「n は正整数」なので、 \lfloor \frac{m}{a} \rfloor \ge 1 であることも確認する必要がある。

d が確定できれば b と c は適当な方法（僕は全探索をした）で決定できる。

上を a を L から R まで動かしながら、 b,\ c が確定できるまで続ける。

むずかしすぎる。

これを ABC で出したときに diff がどうなるか気になる。

提出コード

リンク：http://codeforces.com/contest/1379/submission/87326619

void solve() {
    int Q;
    cin >> Q;
    while (Q--) {
        ll L, R, M;
        cin >> L >> R >> M;
        ll a, b, c;
        ll d;
        for (ll x = L; x <= R; x++) {
            ll q = M / x;
            ll r = M % x;
            // d > 0
            if (q >= 1) {
                if (r >= L - R && r <= R - L) {
                    a = x;
                    d = r;
                    break;
                }
            }
            // d < 0
            r = r - x;
            if (r >= L - R && r <= R - L) {
                a = x;
                d = r;
                break;
            }
        }
 
        for (ll x = L; x <= R; x++) {
            ll y = x + d;
            if (y >= L && y <= R) {
                b = y;
                c = x;
            }
        }
 
        cout << a << " " << b << " " << c << "\n";
    }
}

C - Choosing flowers

解けなかった。「1本だけ購入する花の種類数」を固定して考えてしまい、沼にはまった。

コンテスト後によく考えると、2本以上購入する花は 0 または 1 種類だけだと考えていい *1 ので、「2本以上購入することを許す花」を固定して考えると良いことに気づいた。

k 番目の花を2本以上購入することを許すときの満足度の最大値を求める。

k 番目の花を n 本購入する状態から考え始める。もし、 a_i > b_k となる i が存在するなら k 番目の花の購入数を 1 減らし、 i 番目の花の購入数を1増やすべきである。なので結局、 a_i > b_k である花をすべて、 k番目の花を1つ犠牲にして1本ずつ購入するのが最適である。

この最適解は二分探索で O(\log m) で求められる。これをすべての k \in [1, m] について求め、それらの max を答えとすればいい。計算量は全部で O(m \log m)。

う～～ん、、これは落ち着いていれば解けたんじゃないかな。。。

コンテスト後提出コード

リンク：http://codeforces.com/contest/1379/submission/87344635

void solve() {
    int Q;
    cin >> Q;
    vector<Pll> flws;
    Vl cuma;
    while (Q--) {
        ll N, M;
        cin >> N >> M;
        flws.resize(M);
        for (ll i = 0; i < M; i++) {
            int a, b;
            cin >> a >> b;
            flws[i] = {a, b};
        }
        sort(flws.begin(), flws.end(), greater<Pll>());
 
        cuma.assign(M + 1, 0);
        for (ll i = 0; i < M; i++) {
            cuma[i + 1] = cuma[i] + flws[i].first;
        }
 
        ll ans = 0;
        for (ll i = 0; i < M; i++) {
            auto [ai, bi] = flws[i];
            ll left = -1, right = M;
            while (right - left > 1) {
                ll mid = (left + right) >> 1;
                if (bi < flws[mid].first) {
                    left = mid;
                }
                else {
                    right = mid;
                }
            }
 
            if (right >= N) {
                continue;
            }
 
            ll t;
            if (i < right) {
                t = cuma[right] + bi * (N - right);
            }
            else {
                t = cuma[right] + ai + bi * (N - right - 1);
            }
 
            ans = max(ans, t);
        }
 
        if (N <= M) {
            ans = max(ans, cuma[N]);
        }
 
        cout << ans << "\n";
    }
}

D以降

見てないので割愛。

*1:2本以上購入する花が2種類以上あるとき、 b_i が最大である花の購入数を 1 増やし、その他の花の購入数を 1 減らすことにしても Vladimir の妻の満足度は減らない。