AtCoder Beginner Contest 091 D - Two Sequences
問題
https://beta.atcoder.jp/contests/arc092/tasks/arc092_b
[0<= i <= n-1], [0<= j <= n-1] の i, j について a_i + b_j のそれぞれの xor をとった結果を求めよ。
方針
「桁ごとに独立して考えること」がポイントである。xor演算は繰り上がりがないので各桁ごとに独立して考えて良い。
今 k ビット目 (0-indexed) について考える。k ビット目について考えているので、もとの a[i], b[j] の k+1 ビット目以降は k ビット目の結果に影響を及ぼさないので無視して良く、それぞれ 2k+1 で mod をとる。出力すべき結果の k ビット目は、a[i]+b[j] の k ビット目が 1 になる場合の数の偶奇によって決まる。
a[i]+b[j] の k ビット目が 1 になる場合について考えると、以下の 2 つの場合が考えられる。*
は {0, 1} の任意の数字。
(A)繰り上がりなし
k+2 | k+1 | k | k-1 | ... |
---|---|---|---|---|
* | 0 | 1 | * | ... |
(B)繰り上がりあり
k+2 | k+1 | k | k-1 | ... |
---|---|---|---|---|
* | 1 | 1 | * | ... |
(A) の場合は 2k <= a_i + b_j < 2k+1 となっている必要がある。
(B) の場合は 2k+2k+1 <= a_i + b_j < 2k+1+2k+1 となっている必要がある。
よって、 a[i] を固定すると (A), (B) を満たす b[j] は以下の範囲の数になる。
2k - a[i] <= b_j < 2k+1 - a[i]
2k + 2k+1 - a[i] <= b_j < 2k+1 + 2k+1 - a[i]
これは b[j] をあらかじめソートしておけば二分探索で求めることができる。条件を満たす個数が偶数の場合は k ビット目は 0 になり、奇数の場合は 1 となる。
あとは 0 <= k <= 28 の各 k について求めれば良い。全体の計算量は O(N logN) である。
ACコード
Submission #2593848 - AtCoder Beginner Contest 091
ポイント
- xorはビットごとに独立に考えてみる
- 結果から考える