人生で初めて作った問題。いかがだったでしょうか。
問題へのリンク

略解

解説

この問題において、「支払う金額を各商品の金額の総和で計算する」と問題の設定を変更した場合、これは典型的なナップサック問題と等しくなります。
上記のような設定の変更を行った問題は、 $N$ が充分小さいので半分全列挙+金額に対する二分探索による結果のマージを行うことで解くことができます。
（参考: AtCoder ABC032 D）

しかし、この問題においては「支払う金額を各商品の金額の排他的論理和で計算する」ため単調性が成立しなくなります。なので、金額に対する二分探索による結果のマージは利用できません。

そこで、他の方法による結果のマージを考えます。
まず、商品の集合を2つの集合 $S$ , $T$ に分割するものとします。また、 $S$ および $T$ から選ばれた商品の集合における支払う金額をそれぞれ $x$ , $y$ とします。さらに、最終的に支払う金額を $z = x \oplus y$ とすると、 $z \leq M$ を満たす必要があります。
このとき、 $z$ を2進数表記したもののprefixに関して分類を行うと、
実は高々 $O(\log M)$ 種類しかないことがわかります。
$y = z \oplus x$ より、 $z$ のprefix および $x$ を固定すると $y$ のprefixは一意に定まります。
同じprefixを持つものについてはまとめて計算することが可能（詳細はwriter解を見てください）なので、
$z$ のprefix および $x$ を全探索することで解を求めることができます。
writerの実装の計算量は $O(2^{N/2} N \log M)$ となっています。

prefixに関する分類

「 $z$ を2進数表記したもののprefixに関する分類」について例を用いて説明します。
例えば、 $M$ を10進数表記で 150 とすると、2進数で表すと 10010110 となります。
ここで、0と1のどちらでも良いビットを X と表記することにすると、
$z$ のprefixは必ず以下のどれかになります。

0XXXXXXX
1000XXXX
100100XX
1001010X
10010110

このような分類は、 $z$ の値を最上位ビットから順番に決定していくことで得られます。
$z$ の値が $M$ 未満となることが確定した場合、残りのビットは必ずXとなります。
このような分類の数は、高々 $O(\log M)$ 個しかありません。
（このような分類方法は、桁DPなどで使われている考え方です。けんちょんさんの記事が参考になると思います。）

writer解

#include <algorithm>
#include <iostream>
#include <map>
#include <utility>
#include <vector>

using namespace std;

using ll = long long;
using P = pair<ll, ll>;

constexpr char newl = '\n';
constexpr ll INF = 1e16;

// 半分全列挙する関数
vector<P> rekkyo(int L, int R, vector<ll>& A, vector<ll>& B) {
    int n = R - L;
    map<ll, ll> memo;
    for (int i = 0; i < (1 << n); i++) {
        ll money = 0;
        ll value = 0;
        for (int j = 0; j < n; j++) {
            if (i & (1 << j)) {
                money ^= A[L + j];
                value += B[L + j];
            }
        }
        
        // memo[money] = max(memo[money], value); だけだとダメ！！！
        // memo[money]でやるとデフォルトの値が0になるが、
        // valueが負になる場合があるので死ぬ
        if (memo.find(money) == memo.end()) memo[money] = value;
        else memo[money] = max(memo[money], value);
    }

    vector<P> res;
    for (auto& p : memo) res.push_back(p);
    return res;
}

// 0と1のどちらでも良いビットを切り捨てて、同じprefixのものをまとめていくための関数
vector<P> update(const vector<P>& v, int shift) {
    // rekkyo() により v はソートされており、
    // なおかつ、update()によりソートの順番が崩壊することはないので線形で処理が可能
    if (shift == 0) return v;  // shiftしないなら v は変化しない
    vector<P> nex;
    for (const P& p : v) {
        ll tar = (p.first >> shift);
        if (!nex.empty() && nex.back().first == tar) {
            nex.back().second = max(nex.back().second, p.second);
        } else {
            nex.emplace_back(tar, p.second);
        }
    }
    return nex;
}

ll solve(int N, ll M, vector<ll>& A, vector<ll>& B) {
    vector<P> v1 = rekkyo(0, N / 2, A, B);
    vector<P> v2 = rekkyo(N / 2, N, A, B);

    ll res = 0;
    while (M >= 0) {　// prefixに関する分類をMから順番に降順に見ていく
        for (P& p : v1) {
            ll tar = p.first ^ M;
            auto it = lower_bound(v2.begin(), v2.end(), P(tar, -INF));
            if (it == v2.end()) continue;  // 不正な値にアクセスしないように
            P p2 = *it;
            if (p2.first != tar) continue;
            ll value = p.second + p2.second;
            res = max(res, value);
        }

        if (M == 0) break;
        
        // 次に見るprefixを計算
        int shift = 0;
        while (M > 0 && (M & 1) == 0) {
            M >>= 1;
            shift++;
        }
        M ^= 1;

        v1 = update(v1, shift);
        v2 = update(v2, shift);
    }
    return res;
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);

    int N;
    ll M;
    cin >> N >> M;
    vector<ll> A(N);
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }

    vector<ll> B(N);
    for (int i = 0; i < N; i++) {
        cin >> B[i];
    }

    cout << solve(N, M, A, B) << newl;

    return 0;
}

testerさんに解いてもらった結果、大量の嘘解法と別解が飛び交ってかなり焦りました。別解の中にはwriterの想定解より効率の良い解法もありました。
自力でACできた方も他の解法を考えてみると面白いかもしれません。

ビビジランテソンテネグロホメストーニカルマンドーレポポス

さあ、いつまでたってもオレンジコーダーになれない子はどんどんしまっちゃおうねー

OUPC2020 E. Xor Mart 解説

略解

解説

prefixに関する分類

writer解

コメント