ABC 236

Table of Contents

B - Who is missing?

問題

出現回数が3回の数字を出力すればよい.

愚直に解くと以下のようになる. これで AC は一応取れる.

void solve() {
    int n;
    cin >> n;
    vint card(n + 1);
    rep(i, 4 * n - 1) {
        int a;
        cin >> a;
        card[a]++;
    }

    rep2(i, 1, n + 1) {
        if (card[i] != 4)
            cout << i << endl;
    }
}

別解

数字 $x$ を XOR で偶数回作用させると 0 になり, 奇数回作用させると $x$ になることを思い出すと, 出力すべき数字だけ奇数回だけ出現するので, $XOR(A_1, A_2, \cdots, A_{4N-1})$ が答えとなる.

void solve() {
    int n;
    cin >> n;
    int x = 0;
    rep(i, 4 * n - 1) {
        int y;
        cin >> y;
        x ^= y;
    }
    cout << x << endl;
}

tourist の提出コード を見てこの解放を知った.

提出コード 愚直にカウント 提出コード XOR

D - Dance

問題

解説 AC

$2N$ 人を二人組ずつに分ける組み合わせは

$$ \frac{ \binom{2N}{2} \times \binom{2N-2}{2} \times \cdots \binom{2}{2} }{N!} = \frac{(2N)!}{2^N N!}$$

となる. $N = 8$ のとき, $16! / (2^8 8!) = 2027025$ 通りであるので組み合わせを全列挙して「舞踏会全体の楽しさ」の最大値を求めれば良い.

int n;
vint v, used;
vvint A;

int dfs(int depth) {
    if (depth == n) {
        int ans = 0;
        rep(i, n) ans ^= v[i];
        return ans;
    }
    int ans = 0;
    rep2(i, 2 * n) rep2(j, i + 1, 2 * n) {
        if (!used[i] && !used[j]) {
            used[i] = used[j] = 1;
            v.push_back(A[i][j]);
            chmax(ans, dfs(depth + 1));
            used[i] = used[j] = 0;
            v.pop_back();
        }
    }

    return ans;
}

上のように書くと, 余分な組み合わせまで数えてしまっており, $\binom{2N}{2} \times \binom{2N-2}{2} \times \cdots \binom{2}{2} = 81729648000 (N = 8)$ 通りの組み合わせを数えているせいで TLE になる.

ここで $i$ 個目のペアの一人目は, まだ選ばれていない人のうちの最小の番号の人と固定すると,

int dfs(int depth) {
    if (depth == n) {
        int ans = 0;
        rep(i, n) ans ^= v[i];
        return ans;
    }

    int s = -1;
    rep(i, 2 * n) if (!used[i]) {
        s = i;
        used[s] = 1;
        break;
    }

    int ans = 0;
    rep(j, 2 * n) {
        if (!used[j]) {
            used[j] = 1;
            v.push_back(A[s][j]);
            chmax(ans, dfs(depth + 1));
            v.pop_back();
            used[j] = 0;
        }
    }
    used[s] = 0;

    return ans;
}

提出コード

F - Spices

問題

$(F_2)^N$-ベクトル空間上の XOR と考えると, $(F_2)^N = \mathrm{span}(S)$ となるような基底の集合 $S$ を構成するのに必要なコストの最小値はいくつか？という問題に言い換えられる. これを考えると, スパイスを昇順にソートして, 線形独立となるようにスパイスを選んでいけばよいということがわかる.

線形独立な集合の構成方法は以下のようになる.

for (auto [cost, x] : spices) {
    rep(i, n) if (x >> i & 1) x ^= base[i];
    if (x == 0)
        continue;
    ans += cost;
    rep(i, n) if (x >> i & 1) {
        base[i] = x;
        break;
    }
}

初期値として全ての $i$ に対して base[i] = 0 とする. base[i] != 0 となるような base[i] は $i$ 番目のビットが 1 である数字の代表であり, base[j] (i != j) の数字では $i$ 番目のビットが 0 となっている.

$x$ がすでにピックした数字と線形従属ならば rep(i,n) if (x>>i&1) x ^= base[i]; をすると $0$ となるので, そのスパイスは選ばない. 逆に線形独立だった場合は基底として採用する. rep(i,n) if (x>>i&1) x ^= base[i]; の部分は結局, ガウスの掃き出し法をしているようなものとなっている.

正規直交基底にする場合は(する必要ないけど) rep(i,n) rep(j,n) if ((base[i]>>j&1) && i != j) base[i] ^= base[j]; とするとなる.

提出コード