CS Academy #42 - Xor Submatrix

問題

CS Academy

問題概要

長さの配列と長さの配列が与えられる。これらから、の行列を作る。で行列の各項を与える。 この中で部分行列を取り出し、その部分行列の要素の全てのXORを取る時に、得られる値の最大値を求めよ。

• 
• 

アイデア

部分行列の左上隅のindexを、右下隅のindexをと表すことにしよう。ここで、部分行列内の全てのXORを取るということがどういうことになるのかを考えてみると、各は回だけ全てのXORの計算に現れてくることになる。つまり、このの偶奇によって、各が総和に現れるか否かが決まる事がわかる。

この考察より、以下の3パターンに分けて考えよう：

1. 縦も横も偶数幅
2. 縦か横のどちらか一方が偶数幅でもう片方は奇数幅
3. 縦も横も偶数幅

1の場合については、全ての項が偶数回現れることになるので0になる。2の場合については、奇数幅を構成する側は偶数回現れることになるので打ち消し合い、偶数幅を構成する側のみのXORを取ることになる。3の場合は両方の幅を構成するもののXORを取れば良いことになる。

そうすると、部分行列のとを決めればとについてXORでの累積和を持つことによってこの部分行列内のXOR和をで得ることができる。

よって、部分行列内を全て計算する必要はなく、各配列でそれぞれこのような累積和を取る話に問題は変わってくる。そこで、この問題を言い換えると、

から奇数幅で得られるXOR和の値を集めた集合と、から奇数幅で得られるXOR和の値を集めた集合から1つずつ値を選んでXORを取って最大値を構成するという問題になる。これはTrieを使うことで求められる。具体的には、Vの要素を全てバイナリとして表したものをTrie上にのせ、内の各要素に対して大きいビットの方から貪欲にそのビットを1に出来るならその方向に進むということをすればよい。

実装(C++)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define se second

const int SZ = 2;
struct Trie{
    vector<array<int,SZ>> nodes;

    Trie(){
        nodes.pb({});
    }

    void add(int x){
        int node_num = 0;
        for(int i=29; i>=0; --i){
            int b = x>>i&1;
            // 行き先が無いのでnodeを作成
            if(!nodes[node_num][b]){
                nodes[node_num][b] = nodes.size();
                nodes.pb({});
            }
            node_num = nodes[node_num][b];
        }
    }

    // x との XOR を最大化出来る値を見つける
    int query(int x){
        int ret = 0;
        int node_num = 0;
        for(int i=29; i>=0; --i)
        {
            int b = x>>i&1;
            if(!nodes[node_num][!b]) b = !b;
            node_num = nodes[node_num][!b];
            ret |= (!b)<<i;
        }
        return x^ret;
    }
};

int n,m;
vector<int> v,u;
vector<int> pv,pu;
int XOR(int t, int l, int r)
{
    if(t==0) return pv[r]^pv[l-1];
    else return pu[r]^pu[l-1];
}

int main()
{
    cin >>n >>m;

    v = vector<int>(n+1);
    u = vector<int>(m+1);
    rep(i,n) cin >>v[i+1];
    rep(i,m) cin >>u[i+1];

    pv = vector<int>(n+1);
    for(int i=1; i<=n; ++i) pv[i] = pv[i-1]^v[i];
    pu = vector<int>(m+1);
    for(int i=1; i<=m; ++i) pu[i] = pu[i-1]^u[i];

    int ans = 0;
    // 横方向を偶数長にする
    for(int lx=1; lx<=m; ++lx)for(int rx=lx+1; rx<=m; rx+=2)
    {
        ans = max(ans, XOR(1,lx,rx));
    }
    // 縦方向を偶数長にする
    for(int ly=1; ly<=n; ++ly)for(int ry=ly+1; ry<=n; ry+=2)
    {
        ans = max(ans, XOR(0,ly,ry));
    }

    // 両方奇数長のものを考える
    Trie trie;
    for(int ly=1; ly<=n; ++ly)for(int ry=ly; ry<=n; ry+=2)
    {
        trie.add(XOR(0,ly,ry));
    }
    for(int lx=1; lx<=m; ++lx)for(int rx=lx; rx<=m; rx+=2)
    {
        ans = max(ans,trie.query(XOR(1,lx,rx)));
    }

    cout << ans << endl;
    return 0;
}