ABC 347

Fri, Jan 31, 2025

D - Popcount and XOR

考察

自力で解けたが1日考えた。

$c = \mathrm{popcount}(C)$ とする。$a < b$ として考える。

$X \oplus Y = C$ のことは一旦忘れ $\mathrm{popcount}(X) = a, \mathrm{popcount}(Y) = b$ だけを考える。 $X$, $Y$ で極力同じ場所の bit を立てた場合 $\mathrm{popcount}(X \oplus Y) = |a-b|$。 $X$, $Y$ で同じ場所に bit を建てなかった場合 $\mathrm{popcount}(X \oplus Y) = a+b$ であるから $X \oplus Y = C$ になる必要条件は

$$ |a-b| \leq c \leq a+b $$

である。また同じ場所に立っていた bit を別の場所で立てた場合 popcount の値は2ずつ変わるので $a+b$ と $c$ の parity は同じにならなければならない。

たとえば、下記のように $X$ の 2 bit 目の bit を下げて 4 bit 目を上げると xor を取ると popcount の値が2増える。逆に $X,Y$ のどちらかだけに立っていた bit の位置を1つの場所に移動させると popcount の値が 2 減る。

\begin{align} X = 00111 \Rightarrow X^\prime &= 10011 \nonumber \\ Y &= 01111 \nonumber \end{align}

$X, Y$ で何 bit 同じ場所に bit が立っているかを考える。考えうる popcount の最大値 $a+b$ から最終的に残したい $c$ 個を引いて、残りの bit で pair を作れば良いから $X, Y$ の $\frac{a+b-c}{2}$ 箇所で同じところの bit が立っている。これより $X$ の立っている bit のうち $a - \frac{a+b-c}{2}$ 箇所は $Y$ では立っていない。

解法

$X = 0$ で初期化する。 $C$ のうち bit が立っている $a - \frac{a+b-c}{2}$ 箇所を自由に選んで同じ箇所を $X$ でも立てる。 $C$ のうち bit が立っていない $\frac{a+b-c}{2}$ 箇所を自由に選んで同じ箇所を $X$ では bit を立てる。条件に合うような bit の立て方ができなかったとき -1 を出力。

無事に bit を立て終わったら $Y = X \oplus C$ とする。

void solve() {
    ll a, b, C;
    cin >> a >> b >> C;

    ll c = __builtin_popcountll(C);
    if (c < abs(a - b) || a + b < c || (a + b) % 2 != c % 2) {
        cout << -1 << endl;
        return;
    }

    ll x = 0;
    ll overrap = (a + b - c) / 2;
    a -= overrap;
    rep(i, 60) {
        if (a && (C & (1LL << i))) {
            x ^= 1LL << i;
            a--;
        }
    }
    rep(i, 60) {
        if (overrap && !(C & (1LL << i))) {
            x ^= 1LL << i;
            overrap--;
        }
    }
    if (a || overrap) {  // これがないと 60 60 3 という入力例で WA になる
        cout << -1 << endl;
        return;
    }

    ll y = x ^ C;
    cout << x << ' ' << y << endl;
}

解法2

2026/1/15 追記

DP で解けた。$dp(d,i,j)$ を $X$, $Y$ の $d$ bit 目までの XOR を取ったときに $C$ の $d$ bit 目までの値が一致し、また $X$, $Y$ の立っている bit の数がそれぞれ $i$, $j$ であるような組み合わせが存在するかどうかとする。

$dp(60,a,b)$ が true であれば解が存在する。

遷移は以下の通り

$C$ の $d$ bit 目が 1 のとき

「$X$ の $d$ bit 目が 1, $Y$ の $d$ bit 目が 0」または「$X$ の $d$ bit 目が 0, $Y$ の $d$ bit 目が 1 」のいずれかであるので

\begin{align} dp(d,i,j) = dp(d-1,i-1,j) \lor dp(d-1,i,j-1) \end{align}

$C$ の $d$ bit 目が 0 のとき

[$X$ の $d$ bit 目が 1, $Y$ の $d$ bit 目が 1 」または「$X$ の $d$ bit 目が 0, $Y$ の $d$ bit 目が 0 」のいずれかであるので

\begin{align} dp(d,i,j) = dp(d-1,i-1,j-1) \lor dp(d-1,i,j) \end{align}

復元フェーズでは $dp(60,a,b)$ から逆に辿っていく

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

    ll a, b, C;
    cin >> a >> b >> C;

    C <<= 1;

    int m = 60;
    vector dp(m + 1, vector(m + 1, vint(m + 1)));
    dp[0][0][0] = 1;

    for (int d = 1; d <= m; d++) {
        if (C >> d & 1) {
            rep(i, m + 1) rep(j, m + 1) {
                if (i > 0)
                    chmax(dp[d][i][j], dp[d - 1][i - 1][j]);
                if (j > 0)
                    chmax(dp[d][i][j], dp[d - 1][i][j - 1]);
            }
        } else {
            rep(i, m + 1) rep(j, m + 1) {
                if (i > 0 && j > 0) chmax(dp[d][i][j], dp[d - 1][i - 1][j - 1]);
                chmax(dp[d][i][j], dp[d - 1][i][j]);
            }
        }
    }

    if (dp[m][a][b] == 0) {
        cout << -1 << endl;
        return;
    };

    ll x = 0, y = 0;
    for (int d = 60; d >= 1; d--) {
        if (C >> d & 1) {
            if (b > 0 && dp[d - 1][a][b - 1]) {
                y += 1ll << d;
                b--;
            } else if (a > 0 && dp[d - 1][a - 1][b]) {
                x += 1ll << d;
                a--;
            }
        } else {
            if (dp[d - 1][a][b]) {
                continue;
            } else if (a > 0 && b > 0 && dp[d - 1][a - 1][b - 1]) {
                x += 1ll << d;
                y += 1ll << d;
                a--, b--;
            }
        }
    }

    x >>= 1, y >>= 1;

    cout << x << ' ' << y << endl;
}

E - Set Add Query

https://atcoder.jp/contests/abc347/tasks/abc347_e

2026/1/15 AC

$i$ 回目の操作をしたあとの $S$ の大きさを $T_i$ とし、$\displaystyle f(L,R) = \sum_{i=L}^{R-1} T_i$ とする。

$x$ が出現するタイミングを $x_1, \cdots , x_k$ ($k$ が奇数の場合は末端に $Q$ を追加する)とすると $A_x$ の値は

\begin{align} A_x = f(x_1, x_2) + \cdots + f(x_{k-1}, x_k) \end{align}

となるので $T_i$ の累積和を取っておけば高速に計算できる。

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

    ll N, Q;
    cin >> N >> Q;

    vll X, track;
    vint used(N);
    vvint ids(N);
    ll sum = 0;

    rep(i, Q) {
        ll x;
        cin >> x;
        x--;

        if (used[x])
            sum--;
        else
            sum++;

        used[x] = 1 - used[x];
        track.push_back(sum);
        ids[x].push_back(i);
    }

    vll cm(Q + 1);
    rep(i, Q) {
        cm[i + 1] = cm[i] + track[i];
    }

    rep(i, N) {
        if (ids[i].size() % 2 == 1) ids[i].push_back(Q);
    }

    vll ans(N);
    rep(i, N) {
        for (int j = 0; j < (int)ids[i].size(); j += 2) {
            int l = ids[i][j], r = ids[i][j + 1];
            ans[i] += cm[r] - cm[l];
        }
    }
    print(ans);
}

解説放送でやっていたより洗練された実装

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

    ll N, Q;
    cin >> N >> Q;

    vll A(N);
    unordered_set<ll> st;
    ll sum = 0;

    rep(i, Q) {
        ll x;
        cin >> x;
        x--;

        if (st.count(x)) {
            st.erase(x);
            A[x] += sum;
        } else {
            st.insert(x);
            A[x] -= sum;
        }

        sum += st.size();
    }

    for (ll i : st) A[i] += sum;
    print(A);
}

ABC 347

Table of Contents

D - Popcount and XOR

考察

解法

解法2

E - Set Add Query