ABC 386

Table of Contents

D - Diagonal Separation

https://atcoder.jp/contests/abc386/tasks/abc386_d

解説 AC

黒マスの座標を $(x,y)$ とすると $(i,j) \in [1,x] \times [1,y]$ のマスに白マスが存在しないことが条件である。 与えられたマスを辞書順に sort して上記の条件と合致するか確認する。 頭から順に確認していき

とすればよい。

void solve() {
    int n, m;
    cin >> n >> m;

    vector<tuple<int, int, char>> qs;
    rep(i, m) {
        int x, y;
        char c;
        cin >> x >> y >> c;
        qs.emplace_back(x, y, c);
    }
    sort(all(qs));

    int cnum = INF;
    for (auto [x, y, c] : qs) {
        if (c == 'B') {
            if (cnum <= y) {
                yesno(false);
                return;
            }
        } else {
            chmin(cnum, y);
        }
    }
    yesno(true);
}

E - Maximize XOR

https://atcoder.jp/contests/abc386/tasks/abc386_e

解説 AC

$_N\mathrm{C}_K$ が全列挙可能なときでも $N$ と $K$ の大小関係で場合分けしたほうがよいことがある。

void solve() {
    int n, k;
    cin >> n >> k;

    vll a(n);
    rep(i, n) cin >> a[i];

    bool flip = false;
    if (k > n / 2) {
        flip = true;
        k = n - k;
    }
    ll tot = accumulate(all(a), 0ll, [&](ll acc, ll x) -> ll {
        return acc ^ x;
    });

    ll ans = 0;
    auto dfs = [&](auto dfs, int cnt, int depth, ll sum) {
        if (cnt == k) {
            if (flip) {
                chmax(ans, tot ^ sum);
            } else {
                chmax(ans, sum);
            }
            return;
        }
        if (depth == n)
            return;
        dfs(dfs, cnt, depth + 1, sum);
        dfs(dfs, cnt + 1, depth + 1, sum ^ a[depth]);
    };

    dfs(dfs, 0, 0, 0);
    cout << ans << '\n';
}