ARC092/ABC091 D - Two Sequences

　ARC092/ABC091 D - Two Sequencesを解いていきます。

問題

https://beta.atcoder.jp/contests/arc092/tasks/arc092_b

感想

　本番でC問題も解けず、焦ってこの問題見たら絶望しました。

　何か規則性はないものかと必死で探して見たものの見つからず、解ける気がしませんでした。今後のために解法を書いておく事にしました。

　結果はもちろん0完。。。

解法

　aとbを足した全ての値を全て計算すると、計算量はO(n^2)となり最大で400億になってしまうので間に合わない。

　そこで二進数の各位ごとに計算する。

　　

10進数	2進数
0	0
1	1
2	10
3	11
4	100
5	101
6	110
7	111
8	1000
9	1001
10	1010
11	1011
12	1100
13	1101
14	1110
15	1111
16	10000

　

　この表を見ると2^kの位は０と１が2^k個づつ交互に並んでいることがわかる。

　よって、

　ai + bj の ２^kの位 の値は、ai + bj の値が...

• 　0 ≤ ai+bj < 2^k の時 0
•    2^k ≤ ai+bj < 2*2^k の時 1
•    2*2^k ≤ ai+bj < 3*2^k の時 0
•    3*2^k ≤ ai+bj < 4*2^k の時 1
• 　4*2^k ≤ ai+bj < 5*2^k の時 0
•    5*2^k ≤ ai+bj < 6*2^k の時 1   ......

となる。

　これは、mod(2*2^k)としてしまっても構わないので、

　　　　ai ≡ n (mod 2*2^k)

　　　　bj ≡ m (mod 2*2^k)

　とすると、

• 0 ≤ n+m < 2^k の時 0
• 2^k ≤ n+m < 2*2^k の時 1
• 2*2^k ≤ n+m < 3*2^k の時 0
• 3*2^k ≤ n+m < 4*2^k の時 1

 　n+m < 4*2^k より、場合分けはこれだけで良い。

　xorを出すには各位の1の数がわかればいいので、

　　　　2^k ≤ n+m < 2*2^k

　　　　3*2^k ≤ n+m < 4*2^k

　となるai,bjの組み合わせの総数を求める。

　これは、aiを固定してbを2*2^kで割った時の余りであるmをソートしておくことで、O(log N）で計算することができる。

　↓自分の書いたコード

#include <bits/stdc++.h>

using namespace std;

int main() {
 cin.tie(0);
 ios::sync_with_stdio(false);

 int n;
 long long ans = 0;
 cin >> n;

 vector<int> a(n),b(n);
 vector<int> ma(n),mb(n);

 for (int i = 0;i < n;i++){
  cin >> a[i];
 } 
 for (int i = 0;i < n;i++){
  cin >> b[i];
 }

 long long cnt = 0;

 for (int k = 0;k <= 28;k++){
  long long t = pow(2,k);
  for (int i = 0;i < n;i++){
   ma[i] = a[i] % (2*t);
   mb[i] = b[i] % (2*t);
  }
  sort(mb.begin(),mb.end());
  for (int i = 0;i < n;i++){
   cnt += lower_bound(mb.begin(),mb.end(),2*t-ma[i]) - lower_bound(mb.begin(),mb.end(),t-ma[i]) +
       mb.end() - lower_bound(mb.begin(),mb.end(),3*t-ma[i]);
  }
  if (cnt%2 == 1) ans += t;
  cnt = 0;
 }

 cout << ans << endl;

 return 0;

}