ABC 396

Table of Contents

C - Buy Balls

https://atcoder.jp/contests/abc396/tasks/abc396_c

嘘解法で解いてしまった。配列の範囲外参照していたが AC してしまった。

黒・白ともに降順にソートしておく。 値が正の黒ボールをまず全て取る。その時の数を $N_b$ とする。 次に $N_b$ 個を超えないように正の値の白ボールを取る。その時の数を $N_w$ とする。

$N_w < N_b$ のときは、追加で白ボールをとっても価値は増えないのでこれ以上取る意味はない。

$N_w = N_b$ のときを考える。 このとき、白ボールを取得すると黒ボールの個数を超えてしまうため、黒ボールも同時に取得する必要がある。 よって、追加で白ボールを取ったほうが良い状況は、$B_{N_b+1} + W_{N_w+1} > 0$ が成り立つときである。 これをボールがなくなるか、条件を満たさなくなるまで繰り返す。

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    vll b(n), w(m);
    rep(i, n) cin >> b[i];
    rep(i, m) cin >> w[i];

    sort(rall(b));
    sort(rall(w));

    ll ans = 0;
    int nb = 0;
    rep(i, n) {
        if (b[i] >= 0) {
            ans += b[i];
            nb++;
        }
    }

    int nw = 0;
    while (nw < m && nb > nw && w[nw] > 0) {  // コンテスト中のコードだと nw < m を入れ忘れた
        ans += w[nw];
        nw++;
    }
    while (nw < m && nb < n && w[nw] + b[nb] >= 0) {
        ans += w[nw] + b[nb];
        nw++;
        nb++;
    }
    cout << ans << endl;
}

解説の想定解法

$B_i$, $W_i$ は降順にソートしてあるものとする。

$f_b$, $f_w$, $f_{wmax}$ を以下のように定義する。 \begin{align} f_b(n) &= \sum_{i=1}^n B_i \\ f_w(m) &= \sum_{i=1}^m W_i \\ f_{wmax}(m) &= \max_{i=1}^m f_w(i) \end{align}

$f_{wmax}(m)$ は $m$ 個目までの白ボールからいくつか選んで取ったときの価値の最大値である。

これをつかうと求める答えは

\begin{align} \max(0, \max_{i=1}^{N} \left\{ f_b(i) + f_{wmax}(\min(i,M)) \right\}) \end{align}

である。ここで 0 は何も取らない場合の価値。

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll n, m;
    cin >> n >> m;

    vll b(n), w(m);
    rep(i, n) cin >> b[i];
    rep(i, m) cin >> w[i];

    sort(rall(b));
    sort(rall(w));

    vll cw(m + 1, 0), mcw(m + 1, 0);
    rep(i, m) {
        cw[i + 1] = w[i] + cw[i];
        mcw[i + 1] = max(mcw[i], cw[i + 1]);
    }

    ll ans = 0;
    ll sum = 0;
    rep(i, n) {
        sum += b[i];
        chmax(ans, sum + mcw[min(i + 1, m)]);
    }
    cout << ans << '\n';
}

D - Minimum XOR Path

https://atcoder.jp/contests/abc396/tasks/abc396_d

まず単純パスの長さは $N-1$ 以下である。なぜなら $N$ を超えると同じ頂点を必ず通ることになるからである。

始点を1に固定した場合、単純パスの長さが $m$ となる場合の数は ${}_{N-1} \mathrm{P}_m$ であるから考えうる単純パスの総数は最大で(完全グラフのとき)

$$\sum_{m=1}^{N-1} {}_{N-1} \mathrm{P}_m$$

である。

ここで

\begin{align} \sum_{m=1}^{N-1} {}_{N-1} \mathrm{P}_m < (N-1) (N-1)! < N! \end{align}

であるから $O(N!)$ である。$10! = 3,628,800$ であるから十分間に合う。

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll n, m;
    cin >> n >> m;

    vector<vector<Edge>> graph(n);
    rep(i, m) {
        ll u, v, w;
        cin >> u >> v >> w;
        u--, v--;
        graph[u].push_back({v, w});
        graph[v].push_back({u, w});
    }

    ll ans = INF;

    vint used(n, 0);

    auto dfs = [&](auto dfs, int now = 0, ll sum = 0ll) {
        if (now == n - 1) {
            chmin(ans, sum);
            return;
        }

        for (auto [to, cost] : graph[now]) {
            if (used[to])
                continue;
            used[to] = 1;
            dfs(dfs, to, sum ^ cost);
            used[to] = 0;
        }
    };

    used[0] = 1;
    dfs(dfs);
    cout << ans << endl;
}

E - Min of Restricted Sum

https://atcoder.jp/contests/abc396/tasks/abc396_e

解説 AC

グラフの問題として解く。 XOR なので bit 毎に独立に問題を考えることができる。そうすると各頂点に割り当てられる値は 0 か 1 である。 1箇所が決まると自動的に他の箇所も自動的に決まる。決めているときに矛盾する場合は -1 を出力して終わる。

仮に 0 スタートで割り当てたときの全体の 0 の数と 1 の数を比較して 1 の数が少なければそのまま採用し、多ければ 1 にスタートで割り当てたときの値を採用する。(1 スタートにしたときの数は 0 スタートにしたときの 0,1 の数を swap すればよい)

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    vector<vector<pair<int, int>>> graph(n);
    rep(i, m) {
        int x, y, z;
        cin >> x >> y >> z;
        x--, y--;
        graph[x].emplace_back(y, z);
        graph[y].emplace_back(x, z);
    }

    vint a(n), used(n);

    auto dfs = [&](auto dfs, int now, vint& path) -> void {
        used[now] = 1;
        path.push_back(now);
        for (auto [to, w] : graph[now]) {
            if (used[to]) {
                if (a[to] != (a[now] ^ w)) {
                    cout << -1 << '\n';
                    exit(0);
                }
                continue;
            }
            a[to] = a[now] ^ w;
            dfs(dfs, to, path);
        }
    };

    vvint stock;
    rep(i, n) {
        if (used[i])
            continue;
        vint path;
        dfs(dfs, i, path);
        stock.push_back(path);
    }

    vint na(n);
    for (auto path : stock) {
        int sz = path.size();
        vint cnt(60);
        for (int x : path) {
            rep(i, 60) {
                cnt[i] += ((a[x] >> i) & 1);
            }
        }
        rep(i, 60) {
            if (cnt[i] > sz - cnt[i]) {
                // 1 の数が多い
                // 1 スタートのほうが良かった場合なので i 桁目を全て bit flip させる
                for (int x : path) {
                    a[x] ^= 1ll << i;
                }
            }
        }
    }
    print(a);
}