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はビットごとに独立に考えてみる
  • 結果から考える