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

codeforces.com

ABCDの4完（予言）（システスまだ）。

全部通ればdiv.2内で600位くらいなので成功と言って良さそう。まぁ正のレート変動を得られれば全部成功！！

全体順位は851位。この前のdiv.1は845位でレートそこそこ下がったのに、えでゅふぉなら851位でもレートは上がる(予定)。div.1理不尽～～～

[追記]
システス全部通った。レート変動は1915→1940(+25)。この前のdiv.1の失敗がチャラになった。div.2最高！

A - Bad Triangle

を満たす について が成り立つときこれらを3辺の長さとする三角形は存在しない。

ならば、任意の について が成り立つからこのとき -1 を出力する。 そうでないときは 1,2,N を出力する。

余談だけど prints クラスほんと便利だわ。作ってよかった。

提出コード

リンク： http://codeforces.com/contest/1398/submission/89890485

void solve() {
    int Q;
    cin >> Q;
    Vl A;
    while (Q--) {
        ll N;
        cin >> N;
        A.resize(N);
        for (ll i = 0; i < N; i++) {
            cin >> A[i];
        }
        if (A[0] + A[1] <= A[N - 1]) {
            prints()(1, 2, N);
        }
        else {
            prints()(-1);
        }
    }
}

B -Substring Removal Game

0を消しても相手の有利にしかならない。なので、連続する1を長い順に消去していく。

提出コード

リンク： http://codeforces.com/contest/1398/submission/89897110

void solve() {
    int Q;
    cin >> Q;
    while (Q--) {
        string S;
        cin >> S;
        Vl ns;
        ll cnt = 0;
        for (auto c : S) {
            if (c == '1') {
                ++cnt;
            }
            else {
                ns.emplace_back(cnt);
                cnt = 0;
            }
        }
        if (cnt) {
            ns.emplace_back(cnt);
        }
        sort(ns.begin(), ns.end(), greater<ll>());
        ll ans = 0;
        for (ll i = 0; i < (ll)ns.size(); i += 2) {
            ans += ns[i];
        }
        prints()(ans);
    }
}

C - Good Subarrays

よくみる問題。Educationalみを感じる。

配列を 0-indexed で取って を の総和とすると求めるのは

を満たす の個数。上式を

と変形すれば、もう実家。

提出コード

リンク： http://codeforces.com/contest/1398/submission/89907135

void solve() {
    int Q;
    cin >> Q;
    Vl cum;
    while (Q--) {
        ll N;
        cin >> N;
        string S;
        cin >> S;
        cum.assign(N + 1, 0);
        for (ll i = 0; i < N; i++) {
            cum[i + 1] = cum[i] + (S[i] - '0') - 1;
        }
        map<ll, ll> dp;
        ++dp[0];
        ll ans = 0;
        for (ll i = 1; i <= N; i++) {
            ans += dp[cum[i]];
            ++dp[cum[i]];
        }
        prints()(ans);
    }
}

D - Colored Rectangles

dp[i][j][k] := (赤を i 個、緑を j 個、青を k 個使うときの面積の和の最大値)

としてDP。DはDPのD！

遷移が若干ややこしい？BFSっぽくした。

提出コード

リンク： http://codeforces.com/contest/1398/submission/89927383

ll dp[210][210][210];
bool used[210][210][210];
 
void solve() {
    ll R, G, B;
    cin >> R >> G >> B;
    Vi rs(R), gs(G), bs(B);
    for (ll i = 0; i < R; i++) {
        cin >> rs[i];
    }
    for (ll i = 0; i < G; i++) {
        cin >> gs[i];
    }
    for (ll i = 0; i < B; i++) {
        cin >> bs[i];
    }
    sort(rs.begin(), rs.end(), greater<ll>());
    sort(gs.begin(), gs.end(), greater<ll>());
    sort(bs.begin(), bs.end(), greater<ll>());
 
    using Tup = tuple<ll, ll, ll>;
    queue<Tup> q;
    q.emplace(0, 0, 0);
    used[0][0][0] = true;
    ll ans = 0;
    while (!q.empty()) {
        auto [x, y, z] = q.front();
        q.pop();
        if (x + 1 <= R && y + 1 <= G) {
            dp[x + 1][y + 1][z] = max(dp[x + 1][y + 1][z], dp[x][y][z] + rs[x] * gs[y]);
            ans = max(ans, dp[x + 1][y + 1][z]);
            if (!used[x + 1][y + 1][z]) {
                q.emplace(x + 1, y + 1, z);
                used[x + 1][y + 1][z] = true;
            }
        }
        if (y + 1 <= G && z + 1 <= B) {
            dp[x][y + 1][z + 1] = max(dp[x][y + 1][z + 1], dp[x][y][z] + gs[y] * bs[z]);
            ans = max(ans, dp[x][y + 1][z + 1]);
            if (!used[x][y + 1][z + 1]) {
                q.emplace(x, y + 1, z + 1);
                used[x][y + 1][z + 1] = true;
            }
        }
        if (z + 1 <= B && x + 1 <= R) {
            dp[x + 1][y][z + 1] = max(dp[x + 1][y][z + 1], dp[x][y][z] + rs[x] * bs[z]);
            ans = max(ans, dp[x + 1][y][z + 1]);
            if (!used[x + 1][y][z + 1]) {
                q.emplace(x + 1, y, z + 1);
                used[x + 1][y][z + 1] = true;
            }
        }
    }
    prints()(ans);
}

E - Two Types of Spells

手が届きそうで届かない。60分も費やしたのに......。

「2倍される組」と「等倍組」を2つのsetで管理しようとしたけど実装が発散してむりだった。