スコルの知恵袋

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

Educational Codeforces Round 94 (Rated for Div. 2) 感想

競プロ 競プロ日記

Dashboard - Educational Codeforces Round 94 (Rated for Div. 2) - Codeforces

ABCDの pretest が通ってシステス待ち。かなり遅かったので順位は悪い。かなしいね。

[追記] システス全部通った。レート変動は 1828→1832 (+4)。

前回-112を食らったおかげで4桁順位でもレートが上がってしまった。やったぜ！（やったぜか？）

A - String Similarity

s 中の 0,1 の個数をそれぞれ k_0,k_1 とおく。 k_0 \gt k_1 なら ans = string( n, '0')、そうでなければ、ans = string( n, '1')。

これ思いつくのにめっちゃ時間かかった。

提出コード

リンク： https://codeforces.com/contest/1400/submission/90921500

inline void solve_one() {
    int N;
    cin >> N;
    string S;
    cin >> S;
    int cnt0 = 0, cnt1 = 0;
    for (ll i = 0; i < N * 2 - 1; i++) {
        if (S[i] == '0') {
            ++cnt0;
        }
        else {
            ++cnt1;
        }
    }
    string ans;
    char c;
    if (cnt0 < cnt1) {
        c = '1';
    }
    else {
        c = '0';
    }
    for (ll i = 0; i < N; i++) {
        ans += c;
    }
    prints()(ans);
}
 
void solve() {
    int Q;
    cin >> Q;
    while (Q--) solve_one();
}

B - RPG Protagonist

変数が6個もあると困る。脳のメモリが 3 bit しかない僕にはきつい。

剣も斧も1つ当たりのスコアは1で同じだから、軽い方を優先するべき。

軽い方を全部持っていくことにしても余裕があるとき、follower に持たせる軽い方の個数を固定すると、重い方を持っていく個数が貪欲に求められる。 なので、follower に持たせる軽い方の個数を動かしながら全探索する。

提出コード

リンク： https://codeforces.com/contest/1400/submission/90933779

inline void solve_one() {
    ll p, f;
    cin >> p >> f;
    ll cs, cw;
    cin >> cs >> cw;
    ll s, w;
    cin >> s >> w;
 
    if (w < s) {
        swap(s, w);
        swap(cs, cw);
    }
 
    {
        ll p_ub = p / s;
        ll f_ub = f / s;
        if (p_ub + f_ub <= cs) {
            prints()(p_ub + f_ub);
            return;
        }
    }
 
    ll ans = 0;
    for (ll i = 0; i <= cs; i++) {
        ll x = i;
        ll y = cs - i;
        if (x * s > p || y * s > f) continue;
        ll rp = p - x * s;
        ll rf = f - y * s;
        ll t = 0;
        t += rp / w;
        t += rf / w;
        chmin(t, cw);
        chmax(ans, cs + t);
    }
    prints()(ans);
}
 
void solve() {
    int Q;
    cin >> Q;
    while (Q--) solve_one();
}

C - Binary String Reconstruction

なんかごちゃごちゃしてたら pretest は通ったｗ。

こういうの苦手～～～～ 50分かかったうえ 4WA も出した。

コンテスト後に Twitter を見ると、「対偶を考えよ。」と書いてあった。なるほどな～～！！

もう1年半も競プロしてるのに対偶を考えることも思いつかないんじゃあ競プロ向いてないのかもな......（弱気）

提出コード

リンク： https://codeforces.com/contest/1400/submission/90960842

inline void solve_one() {
    string S;
    cin >> S;
    ll X;
    cin >> X;
    ll n = (ll)S.size();
    bool ok = true;
    string ans;
 
    for (ll i = 0; i < n; i++) {
        ans += '0';
    }
 
    for (ll i = 0; i < n; i++) {
        ll left = i - X;
        ll right = i + X;
        bool is_one_left = false;
        bool is_one_right = false;
        if (left >= 0 && S[left] == '1') {
            is_one_left = true;
        }
        if (right < n && S[right] == '1') {
            is_one_right = true;
        }
        if (is_one_left && is_one_right) {
            ans[i] = '1';
        }
    }
 
    for (ll i = 0; i < n; i++) {
        ll left = i - X;
        ll right = i + X;
        if (ans[i] == '1') {
            S[left] = '0';
            S[right] = '0';
        }
    }
 
    for (ll i = 0; i < X; i++) {
        if (i + X < n && S[i + X] == '1') {
            ans[i] = '1';
            S[i + X] = '0';
        }
    }
 
    for (ll i = n - 1; i >= n - X; i--) {
        if (i - X >= 0 && S[i - X] == '1') {
            ans[i] = '1';
            S[i - X] = '0';
        }
    }
 
    for (ll i = 0; i < n; i++) {
        if (S[i] == '1') {
            ok = false;
            break;
        }
    }
 
    if (ok) {
        prints()(ans);
    }
    else {
        prints()(-1);
    }
}
 
void solve() {
    int Q;
    cin >> Q;
    while (Q--) solve_one();
}

D - Zigzags

アイデア自体は「数列 a について a_i = a_j である (i,j)\ (i \lt j) の個数を求めよ。」という問題の解法と同じ。

「 a_i = a_k かつ a_j = a_l」は「 (a_i,a_j) = (a_k,a_l)」に読み替える。

\displaystyle{ \mathrm{cnt}_{k} [ x ] [ y ] := (i \lt j \lt k\ かつ\ (a_i, a_j) = (x, y)\ を満たす\ (i,j)\ の個数) }

とおくと、解は

\displaystyle{ \mathrm{ans} = \sum_{k=3}^{n-1} \sum_{l=k+1}^{n} \mathrm{cnt}_{k} [ a_k ] [ a_l ] }

と表される。 \mathrm{cnt}_{k+1} [ x ] [ y ] は \mathrm{cnt}_{k} [ x ] [ y ] と a から O(n) で求められる。全体の計算量は O(n^2)。

これは比較的早めに解けた(20分)。CとDは逆に解くべきだったなぁ（後の祭り）。

提出コード

リンク： https://codeforces.com/contest/1400/submission/90970913

ll cnt[3010][3010];
 
inline void solve_one() {
    ll N;
    cin >> N;
    Vl A(N);
    for (ll i = 0; i < N; i++) {
        cin >> A[i];
    }
    for (ll i = 0; i <= N; i++) {
        for (ll j = 0; j <= N; j++) {
            cnt[i][j] = 0;
        }
    }
 
    ll ans = 0;
    for (ll i = 0; i < N; i++) {
        for (ll j = i + 1; j < N; j++) {
            ans += cnt[A[i]][A[j]];
        }
        for (ll j = 0; j < i; j++) {
            ++cnt[A[j]][A[i]];
        }
    }
    prints()(ans);
}
 
void solve() {
    int Q;
    cin >> Q;
    while (Q--) solve_one();
}

E - Clear the Multiset

わからず。

[追記]

解いた。

区間 [0, n) からスタートして、

  • 1番目の操作を区間の最小値が0になるまで繰り返す。そして、0を区切りとして区間を分割する。
  • 2番目の操作で区間の値をすべて0にする。

の2パターンを各区間についてDFSで全探索する。

コンテスト後提出コード

リンク： https://codeforces.com/contest/1400/submission/91038226

void solve() {
    ll N;
    cin >> N;
    Vl A(N);
    for (ll i = 0; i < N; i++) {
        cin >> A[i];
    }
 
    auto dfs = [&](auto&& self, int l, int r) -> ll {
        ll mn = L_INF;
        Vi d;
        for (ll i = l; i < r; i++) {
            if (chmin(mn, A[i])) {
                d.clear();
                d.emplace_back(i);
            }
            else if (mn == A[i]) {
                d.emplace_back(i);
            }
        }
        ll res = r - l;
        ll idx = l;
        ll t = mn;
        for (ll i = l; i < r; i++) {
            A[i] -= mn;
        }
        for (auto k : d) {
            if (k - idx > 0) {
                t += self(self, idx, k);
            }
            idx = k + 1;
        }
        {
            int k = d.back();
            if (r - (k + 1) > 0) {
                t += self(self, k + 1, r);
            }
        }
        for (ll i = l; i < r; i++) {
            A[i] += mn;
        }
        chmin(res, t);
        return res;
    };
 
    ll ans = dfs(dfs, 0, N);
    prints()(ans);
}