解法1. 二分探索
解説 [1] をそのまま参考にした.
ビット単位の排他的論理和はビット単位で独立なので,ビット単位でビットが立っているかどうかを調べる.0-indexed として, ビット目を調べる. とすると,周期 で ビット目が立っているかどうかが分かる.つまり, のいずれかに含まれる自然数は ビット目が0で, のいずれかに含まれる自然数は ビット目が1である.したがって, の各要素をそれぞれ自身の値の による剰余に置き換えると,どの組の和も を満たす.次に, を昇順にソートする. を固定したときに, との和が または に含まれる の要素数を数えると,そのパリティと の ビット目のパリティが一致する.よって,各 の または に含まれる の要素数の総和のパリティが求める値の ビット目のパリティとなる.各ビット毎に のソートが支配的となるために計算時間は となる.また,答えとなるビット数の上限は となり高々30ビットでint型に収まる.しかし,各 ビット目毎の区間に含まれる の要素数の総和の上限は となるため int型に収まらないので注意が必要である.
計算時間:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
cin.tie(0); ios::sync_with_stdio(false);
int n;
cin >> n;
vector<int> a(n), b(n);
for (auto &x : a) cin >> x;
for (auto &x : b) cin >> x;
const int size = log2(*max_element(a.begin(), a.end())
+ *max_element(b.begin(), b.end()));
int ans = 0;
vector<int> bb(n);
for (int i = 0, t = 1; i <= size; ++i) {
for (int j = 0; j < n; ++j)
bb[j] = b[j] % (2 * t);
sort(bb.begin(), bb.end());
ll cnt = 0;
for (int j = 0; j < n; ++j) {
const int aa = a[j] % (2 * t);
cnt += distance(lower_bound(bb.begin(), bb.end(), t - aa),
lower_bound(bb.begin(), bb.end(), 2 * t - aa));
cnt += distance(lower_bound(bb.begin(), bb.end(), 3 * t - aa),
lower_bound(bb.begin(), bb.end(), 4 * t - aa));
}
ans += (cnt % 2) * t;
t *= 2;
}
cout << ans << endl;
return 0;
}
解法2. ループ展開
[2] で参照されているように,ループ展開やSIMDを使うと愚直な二重ループの 時間解法が通る.
次をソースコードに埋め込むとループ展開のオプション -funroll-loops と最適化オプション -O3 が追加される.
#pragma GCC optimize ("-O3", "unroll-loops")
全体でTLEとなるが, のテストケースでTLEだったのが 1685 [ms] と通った.
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize ("-O3", "unroll-loops")
constexpr int MAX_N = 200000;
int n, a[MAX_N], b[MAX_N];
int main() {
scanf("%d", &n);
for (int i = 0; i < n; ++i) scanf("%d", &a[i]);
for (int i = 0; i < n; ++i) scanf("%d", &b[i]);
int ans = 0;
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
ans ^= a[i] + b[j];
printf("%d\n", ans);
return 0;
}
[2] のループ展開を参考に高速化を行った.ポイントとしては,ループ展開されやすいように書き直すのと, int型から unsigned型に変更することである.unsigned型への変更によって のとき, 757 [ms] から 694 [ms] に少しだけの高速化となったが,これが TLE だった他のケースの AC に繋がった( では 1545 [ms] から 1701 [ms]).下にACしたソースコードを載せる.ちなみに,bのブロックサイズを8192から4096に変更すると少し遅くなり,aのブロック化を無くすと TLE となった.
ループ展開の添字でブロックサイズが のとき,残った部分の開始時の添字は & ~ となる.これは, から の による剰余を引いた値となるので, と同じブロックの先頭の要素と等しくなる(どこで参考にしたのか忘れてしまったが面白かったのでメモ).
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize ("-O3", "unroll-loops")
constexpr int MAX_N = 200000;
size_t n;
unsigned a[MAX_N], b[MAX_N];
int main() {
scanf("%lu", &n);
for (size_t i = 0; i < n; ++i) scanf("%u", &a[i]);
for (size_t i = 0; i < n; ++i) scanf("%u", &b[i]);
constexpr size_t block_a = 4, block_b = 8192;
unsigned ans = 0;
for (size_t i = 0; i + (block_a - 1) < n; i += block_a) {
for (size_t j = 0; j + (block_b - 1) < n; j += block_b)
for (size_t k = j; k < j + block_b; ++k) {
ans ^= (a[i] + b[k]) ^ (a[i + 1] + b[k]);
ans ^= (a[i + 2] + b[k]) ^ (a[i + 3] + b[k]);
}
for (size_t j = n & ~(block_b - 1); j < n; ++j) {
ans ^= (a[i] + b[j]) ^ (a[i + 1] + b[j]);
ans ^= (a[i + 2] + b[j]) ^ (a[i + 3] + b[j]);
}
}
for (size_t i = n & ~(block_a - 1); i < n; ++i) {
for (size_t j = 0; j + (block_b - 1) < n; j += block_b)
for (size_t k = j; k < j + block_b; ++k)
ans ^= a[i] + b[k];
for (size_t j = n & ~(block_b - 1); j < n; ++j)
ans ^= a[i] + b[j];
}
printf("%u\n", ans);
return 0;
}
まとめ
排他的論理和は独立性が重要と100回唱える.
ぐらいが3秒で通るのは驚き.
SIMDの解法は時間があったときに [2] と [3] を参考に通してみる.