Codeforces Round #662 (Div. 2) 感想

codeforces.com

ABCDの4完。レート変動は 1939 → 1993 (+54)。やったね！

最近こどふぉは成功が続いててうれしい。（一方、AtCoderさんは......）

rated内順位は332位で、これはdiv.2の中では最高順位！

ところで今回は英語がめっちゃ読みにくくてしんどかった。

A - Rainbow Dash, Fluttershy and Chess Coloring

かなり時間がかかった（18分）。フレンドの同レート帯の人たちはだいたい7分くらいで解いてるのでこれはかなり遅い。

n = 3, 4, 5, 6, 7 あたりまで調べてもなんかよくわからず色々迷走した（提出コードにも迷走の跡が残っている）。

しばらく経って、正方形の中央に到達するまでの手数に注目して、

• が奇数のとき、
• が偶数のとき、

かな～～という気分になったけど、 結局証明はできなくて祈りながら提出した。

書きながら気づいたけど、これ別に偶奇で分ける必要なくて でいいな。

提出コード

リンク： http://codeforces.com/contest/1393/submission/89224561

void solve() {
    int Q;
    cin >> Q;
    while (Q--) {
        ll N;
        cin >> N;
        if (N % 4 == 0) {
            prints()(N / 2 + 1);
        }
        else if (N % 4 == 1) {
            prints()((N + 1) / 2);
        }
        else if (N % 4 == 2) {
            prints()(N / 2 + 1);
        }
        else {
            prints()((N + 1) / 2);
        }
    }
}

B - Applejack and Storages

2本以上ある長さの種類数(cnt2)、4本以上ある長さの種類数(cnt4)、6本以上ある長さの種類数(cnt6)、8本以上ある長さの種類数(cnt8)をそれぞれ管理する。

正方形と長方形を作る方法には、

1. 正方形：、長方形：
2. 正方形：、長方形：
3. 正方形：、長方形：
4. 正方形：、長方形：

があって、それぞれ

1. cnt8 ≧ 1
2. cnt6 ≧ 1 かつ cnt2 ≧ 2
3. cnt4 ≧ 2
4. cnt4 ≧ 1 かつ cnt2 ≧ 3

が満たされていれば実現できるから、これらのいずれかが成り立てば YES。

提出コード

リンク：http://codeforces.com/contest/1393/submission/89239737

void solve() {
    ll N;
    cin >> N;
    Vl ns(100001);
    for (ll i = 0; i < N; i++) {
        ll a;
        cin >> a;
        ++ns[a];
    }
    ll cnt8 = 0, cnt6 = 0, cnt4 = 0, cnt2 = 0;
    for (ll i = 0; i <= 100000; i++) {
        if (ns[i] >= 8) {
            ++cnt8, ++cnt6, ++cnt4, ++cnt2;
        }
        else if (ns[i] >= 6) {
            ++cnt6, ++cnt4, ++cnt2;
        }
        else if (ns[i] >= 4) {
            ++cnt4, ++cnt2;
        }
        else if (ns[i] >= 2) {
            ++cnt2;
        }
    }
 
    int Q;
    cin >> Q;
    while (Q--) {
        char f;
        ll x;
        cin >> f >> x;
        if (f == '+') {
            ++ns[x];
            if (ns[x] == 8) {
                ++cnt8;
            }
            else if (ns[x] == 6) {
                ++cnt6;
            }
            else if (ns[x] == 4) {
                ++cnt4;
            }
            else if (ns[x] == 2) {
                ++cnt2;
            }
        }
        else {
            --ns[x];
            if (ns[x] == 7) {
                --cnt8;
            }
            else if (ns[x] == 5) {
                --cnt6;
            }
            else if (ns[x] == 3) {
                --cnt4;
            }
            else if (ns[x] == 1) {
                --cnt2;
            }
        }
        bool ok = false;
        if (cnt8 >= 1) {
            ok = true;
        }
        else if (cnt6 >= 1 && cnt2 >= 2) {
            ok = true;
        }
        else if (cnt4 >= 2) {
            ok = true;
        }
        else if (cnt4 >= 1 && cnt2 >= 3) {
            ok = true;
        }
 
        prints()(ok ? "YES" : "NO");
    }
}

C - Pinkie Pie Eats Patty-cakes

これが早く解けたのが良かった。

一番多く登場する数を均等に分布させて、残りはそれに沿うように配置すればいい。 例えば、n = 9, a = {1, 1, 1, 2, 2, 2, 3, 3, 4} なら

1, 2, 3, 4, 1, 2, 3, 1, 2

登場回数の最大値を 、登場回数が と等しい数の種類数を とおくと

提出コード

リンク：http://codeforces.com/contest/1393/submission/89248350

void solve() {
    int Q;
    cin >> Q;
    Vl ns;
    while (Q--) {
        ll N;
        cin >> N;
        ns.assign(N + 1, 0);
        for (ll i = 0; i < N; i++) {
            ll a;
            cin >> a;
            ++ns[a];
        }
        ll mx = 0, cnt = 0;
        for (ll i = 1; i <= N; i++) {
            if (ns[i] > mx) {
                mx = ns[i];
                cnt = 1;
            }
            else if (ns[i] == mx) {
                ++cnt;
            }
        }
        prints()((N - cnt) / (mx - 1) - 1);
    }
}

D - Rarity and New Dress

これが解けたのうれしい。提出はコンテスト終了3分前だった。

図を描いて考察していると、答えは「各マスにおける色の境界または壁との最小距離の和」であることが分かったのでこれをBFSで求めた。

例えば、

ｂｂａａａｂｂ
ｂｂｂａａａｂ
ａｂａａａａａ
ｂｂｂａａａｂ
ａｂａａａｂｂ

の場合、各マスにおける色の境界または壁との最小距離は

１１１１１１１
１２１１２１１
１１１２３２１
１２１１２１１
１１１１１１１

となる。

計算量は 。

提出コード

リンク： http://codeforces.com/contest/1393/submission/89248350

char cell[2001][2001];
int checked[2001][2001];
 
void solve() {
    ll N, M;
    cin >> N >> M;
    for (ll i = 0; i < N; i++) {
        string s;
        cin >> s;
        for (ll j = 0; j < M; j++) {
            cell[i][j] = s[j];
        }
    }
    using Tup = tuple<ll, ll, ll>;
    queue<Tup> q;
    constexpr array<ll, 2> steps[] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    ll ans = 0;
    for (ll i = 0; i < N; i++) {
        for (ll j = 0; j < M; j++) {
            ++ans;
            for (ll k = 0; k < 4; k++) {
                ll nx = i + steps[k][0];
                ll ny = j + steps[k][1];
                if (nx >= 0 && nx < N && ny >= 0 && ny < M) {
                    if (cell[i][j] != cell[nx][ny]) {
                        checked[i][j] = 1;
                        q.emplace(i, j, 1);
                        break;
                    }
                }
                else {
                    checked[i][j] = 1;
                    q.emplace(i, j, 1);
                }
            }
        }
    }
    while (!q.empty()) {
        auto [x, y, d] = q.front();
        q.pop();
        for (ll i = 0; i < 4; i++) {
            ll nx = x + steps[i][0];
            ll ny = y + steps[i][1];
            if (nx >= 0 && nx < N && ny >= 0 && ny < M) {
                if (cell[x][y] == cell[nx][ny] && checked[nx][ny] == 0) {
                    ans += d;
                    q.emplace(nx, ny, d + 1);
                    checked[nx][ny] = 1;
                }
            }
        }
    }
    prints()(ans);
}