Codeforces Round #663 (Div. 2) 感想

ABCの3完。1993→1940 (-53)。いってぇ

Dをしょうもないミスで落としたの痛いなぁ。

A - Suborrays

1, 2, ..., n を出力しましょう（笑）

提出コード

リンク： http://codeforces.com/contest/1391/submission/89411895

void solve() {
    int Q;
    cin >> Q;
    while (Q--) {
        ll N;
        cin >> N;
        for (ll i = 0; i < N; i++) {
            prints("", " ")(i + 1);
        }
        prints()();
    }
}

B - Fix You

右端と下端を見ましょう（笑）。ここまでギャグ。

提出コード

リンク： http://codeforces.com/contest/1391/submission/89419594

void solve() {
    int Q;
    cin >> Q;
    while (Q--) {
        ll N, M;
        cin >> N >> M;
        ll ans = 0;
        for (ll i = 0; i < N; i++) {
            string s;
            cin >> s;
            if (i < N - 1) {
                if (s[M - 1] == 'R') {
                    ++ans;
                }
            }
            else {
                for (ll j = 0; j < M; j++) {
                    if (s[j] == 'D') {
                        ++ans;
                    }
                }
            }
        }
        prints()(ans);
    }
}

C - Cyclic Permutations

極小値を持つ ⇔ cyclic。極小値を持たないのは $2^{n-1}$ 通りだからこれを全体から引けばいい。

提出コード

リンク： http://codeforces.com/contest/1391/submission/89434108

// ModInt 略

constexpr ll MOD = 1e9 + 7;
using Mint = ModInt<MOD>;
 
void solve() {
    ll N;
    cin >> N;
    Mint ans = 1;
    for (ll i = 1; i <= N; i++) {
        ans *= i;
    }
    ans -= Mint(2).pow(N - 1);
    prints()(ans);
}

D - 505

2 × 2 の正方形が奇数個の1しか持たないとき 4 × 4 の正方形はどうあがいても偶数個の1を持つから、 $\min(n, m) \ge 4$ なら -1。

また、 $\min(n, m) = 1$ なら 0。

以下、 $\min(n, m) = 2, 3$ のときを考える。 $n \le m$ を仮定する(そうでないなら転置する)。

$\min(n, ,m) = 2$ のとき、 $a_{1,1} + a_{2,1}$ の偶奇を決めると、すべての $1 \le j \le m$ について $a_{1,j} + a_{2,j}$ の偶奇が決定される。具体的には、偶奇偶奇・・・か奇偶奇偶・・・のどちらかになる。現在の状態から「偶奇偶奇・・・」または「奇偶奇偶・・・」にするための最小の操作数はすぐに求められる。2マスの和を偶数にするのは (0, 0)と(1, 1)、奇数にするのは (0, 1)と(1, 0) で、現在の状態からより少ない手で実現できる方を選んでいけばいい。

$\min(n, ,m) = 3$ のときも上と似ていて、 $a_{1,1} + a_{2,1}$ と $a_{2,1} + a_{3,1}$ の偶奇を決めるとすべての $1 \le j \le m$ について $a_{1,j} + a_{2,j}$ および $a_{2, j} + a_{3,j}$ の偶奇が決定されることを使って頑張る。

ここまでわかっていたのにACをとれず......。理由はマスの配列の大きさを $\min(n, ,m) = 3$ のときをベースにして 3 × 340000 で取っていて、 $\min(n, ,m) = 2$ のとき配列外参照を起こしているのに気がつかなかったから。まじで勘弁してくれ。

コンテスト後提出コード

リンク： http://codeforces.com/contest/1391/submission/89454668

bool cell[510000][3];
 
void solve() {
    ll N, M;
    cin >> N >> M;
    if (min(N, M) >= 4) {
        prints()(-1);
        return;
    }
    if (min(N, M) == 1) {
        prints()(0);
        return;
    }
    bool is_trans = N < M;
    string s;
    for (ll i = 0; i < N; i++) {
        cin >> s;
        for (ll j = 0; j < M; j++) {
            if (is_trans) {
                cell[j][i] = s[j] == '1';
            }
            else {
                cell[i][j] = s[j] == '1';
            }
        }
    }
    if (is_trans) {
        swap(N, M);
    }
 
    ll ans = L_INF;
 
    if (M == 2) {
        int cnt1 = 0, cnt2 = 0;
        bool is_even = true;
        for (ll i = 0; i < N; i++) {
            int a = cell[i][0];
            int b = cell[i][1];
 
            int tmp1 = (int)(a != 0) + (int)(b != 0);
            int tmp2 = (int)(a != 1) + (int)(b != 1);
 
            int tmp3 = (int)(a != 0) + (int)(b != 1);
            int tmp4 = (int)(a != 1) + (int)(b != 0);
 
            if (is_even) {
                cnt1 += min(tmp1, tmp2);
                cnt2 += min(tmp3, tmp4);
            }
            else {
                cnt2 += min(tmp1, tmp2);
                cnt1 += min(tmp3, tmp4);
            }
 
            is_even ^= true;
        }
        ans = min(cnt1, cnt2);
    }
    else {
        int cnt_ee = 0;
        int cnt_oo = 0;
        int cnt_eo = 0;
        int cnt_oe = 0;
        bool is_even = true;
        for (ll i = 0; i < N; i++) {
            int a = cell[i][0];
            int b = cell[i][1];
            int c = cell[i][2];
 
            int tmp1 = (int)(a != 0) + (int)(b != 0) + (int)(c != 0);
            int tmp2 = (int)(a != 1) + (int)(b != 1) + (int)(c != 1);
 
            int tmp3 = (int)(a != 0) + (int)(b != 1) + (int)(c != 0);
            int tmp4 = (int)(a != 1) + (int)(b != 0) + (int)(c != 1);
 
            int tmp5 = (int)(a != 0) + (int)(b != 0) + (int)(c != 1);
            int tmp6 = (int)(a != 1) + (int)(b != 1) + (int)(c != 0);
 
            int tmp7 = (int)(a != 0) + (int)(b != 1) + (int)(c != 1);
            int tmp8 = (int)(a != 1) + (int)(b != 0) + (int)(c != 0);
 
            if (is_even) {
                cnt_ee += min(tmp1, tmp2);
                cnt_oo += min(tmp3, tmp4);
                cnt_eo += min(tmp5, tmp6);
                cnt_oe += min(tmp7, tmp8);
            }
            else {
                cnt_oo += min(tmp1, tmp2);
                cnt_ee += min(tmp3, tmp4);
                cnt_oe += min(tmp5, tmp6);
                cnt_eo += min(tmp7, tmp8);
            }
 
            is_even ^= true;
        }
        ans = min({cnt_ee, cnt_oo, cnt_eo, cnt_oe});
    }
    prints()(ans);
}

スコルの知恵袋

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

Codeforces Round #663 (Div. 2) 感想

A - Suborrays

B - Fix You

C - Cyclic Permutations

D - 505