CS Academy Round 42 - Xor Submatrix
N次元ベクトルVとM次元ベクトルUが与えられる。i行j列の要素が V[i] xor U[j] であるようなN x M行列を考える。この行列の行の連続する部分列、及び列の連続する部分列からなる小行列について、その小行列の全要素のxorをスコアとするとき、スコアの最大値を求めよ。
a xor a = 0とかxorの可換性を使う。例えば小行列の行また列が偶数次元の場合、対応する列または行は偶数回xorされることになり、結局0になる。そのため偶数次元側の行または列のxorを考えるだけでよい。
また、小行列の行も列も奇数次元のとき、結局偶数個のxorは0になるので、行と列を独立してxorを計算し、それらの組み合わせのxorの最大値を求めればよい。ただしまともにやると行や列それぞれがO(N^2)なので、それらの組み合わせでO(N^4)かかるがこれではTLEする。そこで、行の各部分列について、最大になるような列の部分列のxorをO(logN)で求めるためにTrie木を構成しておく。するとO(N^2 logN)で計算可能である。
最後のO(logN)はTrie木の他に、列をソートしておいてbitごとにBinary Searchしてもよいが、若干実装が複雑になる。
