Hello world!

WordPress へようこそ。これは最初の投稿です。編集もしくは削除してブログを始めてください !

(BIT・バブルソートの交換回数・反転数)ARC-088-E-Papple Sort

問題URL→https://beta.atcoder.jp/contests/arc088/tasks/arc088_c

注意
BITは1-indexedなので0-indexed想定すると無限ループする!!!

解説を見てコードは自分で書いた。
まず奇数個の文字が2種類以上あるとダメで-1を出力する。
そうでない場合回文に出来る。

まず各文字のうち半分は左側、もう半分は右側に移動させないといけない。
さらに同じ文字をスワップするのは無駄なので同じ文字の登場順は元の文字列と同じ。
ここまでの考察で構成する回文の左側に登場する文字の種類と個数は分かった。
そのうち元の登場順の通りに並べた左側の文字列がそのまま構成する回文の左側となる。
左側の文字列をスワップするのは右側の文字列をスワップするのと同じで、ならばスワップは右側に任せる。
そうすると最終的な回文が得られる。

後は蟻本に書いてあるバブルソートの交換回数を実装するのみ。初めて実装した。
あまりきれいなコードではないけれど一応AC

#include <iostream>
#include <vector>
#include <string.h>
#include <stack>
#include <queue>
#include <algorithm>
#include <climits>
#include <cmath>
#include <map>
#include <set>
#include <assert.h>
#include <numeric>
#define REP(i,n) for(ll i=0;i<(n);i++)
#define MOD 1000000007
#define pb push_back
#define int long long
#ifdef int
const long long INF = LLONG_MAX / 10;
#else
const int INF = 1010101010;
#endif
using namespace std;
typedef long long ll;
typedef vector<int> vint;
typedef vector<vector<ll> > mat;
typedef pair<int, int> P;
//typedef pair<double, double> P;
const int dx[9] = {-1, 0, 0, 1, -1, -1, 1, 1, 0};
const int dy[9] = {0, -1, 1, 0, -1, 1, -1, 1, 0};


const int MAX_N = 202020;
int bit[MAX_N + 1], n = 202020;
int sum(int i) {
  // cout << "AAAAAA " << i << endl;
  int s = 0;
  while (i > 0) {
    // cout << "BABA" << endl;
    s += bit[i];
    i -= i & -i;
  }
  return s;
}
void add(int i, int x) {
  // cout << i << "-" << x << endl;
  while (i <= n) {
    bit[i] += x;
    i += i & -i;
  }
}

string S;
map<char, int> cnt;
map<char, vector<int>> idx;
 
signed main()
{
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  cin >> S;
  int N = S.length();

  for (int i=0; i<N; i++) {
    cnt[S[i]]++;
    idx[S[i]].pb(i);
  }

  int oddnum = 0;
  char oddchar;
  for (auto it=cnt.begin(); it!=cnt.end(); it++) {
    if (it->second & 1) {
      oddchar = it->first;
      oddnum++;
    }
  }
  if (2 <= oddnum) {
    cout << -1 << endl;
    return 0;
  }

  string left;
  map<char, int> usenum;
  for (int i=0, len=0; i<N && len<N/2; i++) {
    if (usenum[S[i]] < cnt[S[i]] / 2) {
      left += S[i];
      usenum[S[i]]++;
      len++;
    }
  }
  int len = left.length();
  string full = left;
  if (N & 1) full += oddchar;
  for (int i=len-1; i>=0; i--) {
    full += left[i];
  }

  vector<int> a;
  usenum.clear();
  for (char c : full) {
    a.pb(idx[c][usenum[c]++]);
  }

  // cout << full << endl;
  // for (int i : a) cout << i << " ";

  int ans = 0;
  for (int j=0; j<N; j++) {
    // cout << "AAA" << endl;
    ans += j - sum(a[j] + 1);
    add(a[j] + 1, 1);
  }

  // cout << full << endl;
  // for (int i : a) cout << i << " ";
  cout << ans << endl;
}

(BIT・区間)ARC-068-E-Snuke Line

問題URL→https://beta.atcoder.jp/contests/arc068/tasks/arc068_c

解説と上位陣のコードを見た。

重要ポイントは各dについてd-1<=r-lの区間は必ず取れるということ。

なので、r-lがd-2以下の各区間について何個取れるかを調べればいい。

各dについてr-lがd-2以下の区間は必ず一回ずつ取れるので、d-2以下の区間をいもす法のように区間を塗りつぶして

後から各停車駅で取れるのを計算すればいい。

ただしいもす法だと計算量が間に合わない(たぶん)のでBITで管理するといい。

他の人のコードを参考に自分で書いたコード

#include <iostream>
#include <vector>
#include <string.h>
#include <stack>
#include <queue>
#include <algorithm>
#include <climits>
#include <cmath>
#include <map>
#include <set>
#include <assert.h>
#include <numeric>
#define REP(i,n) for(ll i=0;i<(n);i++)
#define MOD 1000000007
#define pb push_back
#define int long long
#ifdef int
const long long INF = LLONG_MAX / 10;
#else
const int INF = 1010101010;
#endif
using namespace std;
typedef long long ll;
typedef vector<int> vint;
typedef vector<vector<ll> > mat;
typedef pair<int, int> P;
//typedef pair<double, double> P;
const int dx[9] = {-1, 0, 0, 1, -1, -1, 1, 1, 0};
const int dy[9] = {0, -1, 1, 0, -1, 1, -1, 1, 0};


//BIT [1,n]
//sum(i) : a1+a2+a3+・・・・+aiを計算する
//add(i,x) : ai+=x
const int MAX_N = 202020;
int bit[MAX_N + 1], n = 202020;

int sum(int i) {
  int s = 0;
  while (i > 0) {
    s += bit[i];
    i -= i & -i;
  }
  return s;
}

void add(int i, int x) {
  while (i <= n) {
    bit[i] += x;
    i += i & -i;
  }
}


int N, M;
vector<P> arr[101010];

signed main()
{
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  cin >> N >> M;
  REP(i,N) {
    int l, r;
    cin >> l >> r;
    arr[r-l].pb({l, r});
  }

  int exclude = 0;
  for (int d=1; d<=M; d++) {
    if (d == 1) {
      cout << N << endl;
    } else {
      for (auto p : arr[d-2]) {
        add(p.first, 1);
        add(p.second + 1, -1);
      }
      exclude += arr[d-2].size();
      int ans = N - exclude;
      for (int x=0; x<=M; x+=d) {
        ans += sum(x);
      }
      cout << ans << endl;
    }
  }
}

参考にしたlatte0119さんのコード

#include<bits/stdc++.h>
using namespace std;

#define int long long
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define all(v) (v).begin(),(v).end()
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define pb push_back
#define fi first
#define se second
template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

struct BIT{
    int N;
    vector<int>dat;
    void init(int n){
        N=n;
        dat.resize(N+1);
    }
    BIT(){}
    BIT(int n){init(n);}

    void add(int k,int x){
        for(k++;k<=N;k+=k&-k)dat[k]+=x;
    }
    int sum(int k){
        int ret=0;
        for(k++;k;k-=k&-k)ret+=dat[k];
        return ret;
    }
};

int N,M;
vint lis[111111];

signed main(){
    scanf("%lld%lld",&N,&M);
    rep(i,N){
        int l,r;
        scanf("%lld%lld",&l,&r);
        r++;
        lis[r-l].pb(l);
    }

    BIT bit;bit.init(M+114);
    int latte=N;
    for(int d=1;d<=M;d++){
        for(auto l:lis[d]){
            int r=l+d;
            bit.add(r,-1);bit.add(l,1);
        }
        latte-=lis[d].size();
        int ans=latte;
        for(int x=d;x<=M;x+=d)ans+=bit.sum(x);
        printf("%lld\n",ans);
    }
    return 0;
}

(グラフ・木・パリティチェック)ARC-063-E-木と整数 / Integers on a Tree

問題URL→https://beta.atcoder.jp/contests/arc063/tasks/arc063_c

解説とsemiexpさんのコードを見た。

木の問題なので根付き木として考える。全ての書き込み済みの整数についてその深さと書いてある値のxorのパリティが全て一致する必要がある。
それを判定するコードはsemiexpさんのコードのように書けばいい。
後は各頂点についてlowとhighの値を更新する。

C++はputsとcoutを両方書くとなぜか通らない。
コードはsemiexpさんのを参考にさせていただいた。

#include <iostream>
#include <vector>
#include <string.h>
#include <stack>
#include <queue>
#include <algorithm>
#include <climits>
#include <cmath>
#include <map>
#include <set>
#include <assert.h>
#include <numeric>
#define REP(i,n) for(ll i=0;i<(n);i++)
#define MOD 1000000007
#define int long long
#ifdef int
const long long INF = LLONG_MAX / 10;
#else
const int INF = 1010101010;
#endif
using namespace std;
typedef long long ll;
typedef vector<vector<ll> > mat;
typedef pair<int, int> P;
//typedef pair<double, double> P;
const int dx[9] = {-1, 0, 0, 1, -1, -1, 1, 1, 0};
const int dy[9] = {0, -1, 1, 0, -1, 1, -1, 1, 0};

int N;
int A, B;

vector<int> graph[101010];
int X[101010];
int low[101010], hi[101010];
int dep[101010];

void dfs(int p, int rt, int d) {
  dep[p] = d;
  for (int q : graph[p]) if (q != rt) {
    dfs(q, p, d + 1);
    low[p] = max(low[p], low[q] - 1);
    hi[p] = min(hi[p], hi[q] + 1);
  }
}

void dfs2(int p, int rt) {
  for (int q : graph[p]) if (q != rt) {
    low[q] = max(low[q], low[p] - 1);
    hi[q] = min(hi[q], hi[p] + 1);
    dfs2(q, p);
  }
}

signed main()
{
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  cin >> N;
  REP(i,N-1) {
    cin >> A >> B;
    A--; B--;
    graph[A].push_back(B);
    graph[B].push_back(A);
  }
  REP(i,N) {
    X[i] = -INF;
    low[i] = -INF;
    hi[i] = INF;
  }
  int K;
  cin >> K;
  while (K--) {
    int v, p;
    cin >> v >> p;
    v--;
    X[v] = low[v] = hi[v] = p;
  }

  dfs(0, -1, 0);
  dfs2(0, -1);

  int par = -1;
  REP(i,N) {
    if (X[i] != -INF) {
      int myp = (X[i] ^ dep[i]) & 1;
      if (par == -1) par = myp;
      if (par != myp) {
        puts("No");
        return 0;
      }
    }
    if (low[i] > hi[i]) {
      puts("No");
      return 0;
    }
  }

  puts("Yes");
  // REP(i,N) cout << low[i] << endl;
  REP(i,N) printf("%lld\n", low[i]);
}

こちらはsugim48さんの解き方。
考え方としては決まっている値の小さいところから隣に+1した値を書いていく。
書いたところをpriority_queueで管理する。
最後に全ての頂点と隣接点の差が1であるかチェックする。
すごくシンプルだしコードも短くてすむので良いと思った。

#include <iostream>
#include <vector>
#include <string.h>
#include <stack>
#include <queue>
#include <algorithm>
#include <climits>
#include <cmath>
#include <map>
#include <set>
#include <assert.h>
#include <numeric>
#define REP(i,n) for(ll i=0;i<(n);i++)
#define MOD 1000000007
#define pb push_back
#define int long long
#ifdef int
const long long INF = LLONG_MAX / 10;
#else
const int INF = 1010101010;
#endif
using namespace std;
typedef long long ll;
typedef vector<vector<ll> > mat;
// typedef pair<int, int> P;
typedef pair<int, int> i_i;
//typedef pair<double, double> P;
const int dx[9] = {-1, 0, 0, 1, -1, -1, 1, 1, 0};
const int dy[9] = {0, -1, 1, 0, -1, 1, -1, 1, 0};

int N;
int A, B;

signed main()
{
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  cin >> N;
  vector<vector<int>> G(N);
  REP(i,N-1) {
    cin >> A >> B;
    A--; B--;
    G[A].pb(B);
    G[B].pb(A);
  }
  vector<int> d(N, -1LL);
  priority_queue<i_i, vector<i_i>, greater<i_i>> pq;  //昇順に取り出す
  int K;
  cin >> K;
  while (K--) {
    int v, p;
    cin >> v >> p;
    v--;
    d[v] = p;
    pq.push(i_i(p, v));
  }
  while (!pq.empty()) {
    i_i p = pq.top(); pq.pop();
    int u = p.second;
    for (int v : G[u]) {
      if (d[v] == -1LL) {
        d[v] = d[u] + 1;
        pq.push(i_i(d[v], v));
      }
    }
  }
  REP(u,N) {
    for (int v : G[u]) {
      if (abs(d[u] - d[v]) != 1LL) {
        cout << "No" << endl;
        return 0;
      }
    }
  }

  cout << "Yes" << endl;
  REP(u,N) cout << d[u] << endl;
}

(ダブリング)ARC-060-E-高橋君とホテル/Tak and Hotels

問題URL→https://beta.atcoder.jp/contests/arc060/tasks/arc060_c

分からなかったので解説と1位だったsemiexpさんのコードを見た。
ダブリングというテクを使わないと解けない問題だった。

ダブリングについての詳しい解説は以下のsatanicさんのブログが詳しいし分かりやすい。
http://satanic0258.hatenablog.com/entry/2017/02/23/222647

簡単に説明するとN個次の要素を高速に求めたいときに、
前処理O(MlogM) ※Mは全体の要素数
クエリO(logN)
で求められるようにする技術。
詳しくはsatanicさんのブログを参照。

とりあえずコードはsemiexpさんのを写経したもの。

後でsatanic式ダブリングを使ったコードを書こう。

#include <iostream>
#include <vector>
#include <string.h>
#include <stack>
#include <queue>
#include <algorithm>
#include <climits>
#include <cmath>
#include <map>
#include <set>
#include <assert.h>
#include <numeric>
#define REP(i,n) for(ll i=0;i<(n);i++)
#define MOD 1000000007
#define int long long
#ifdef int
const long long INF = LLONG_MAX / 10;
#else
const int INF = 1010101010;
#endif
using namespace std;
typedef long long ll;
typedef vector<vector<ll> > mat;
typedef pair<int, int> P;
//typedef pair<double, double> P;
const int dx[9] = {-1, 0, 0, 1, -1, -1, 1, 1, 0};
const int dy[9] = {0, -1, 1, 0, -1, 1, -1, 1, 0};

int N, L, Q;
int x[101010];
int bk[17][101010];
 
signed main()
{
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  cin >> N;
  REP(i,N) cin >> x[i];
  cin >> L >> Q;

  int pre = 0;
  for (int i=0; i<N; i++) {
    while (x[i] - x[pre] > L) pre++;
    bk[0][i] = pre; //i番目の頂点から次に行ける最も左の頂点番号
  }

  for (int i=1; i<17; i++) {
    for (int j=0; j<N; j++) {
      bk[i][j] = bk[i-1][ bk[i-1][j] ];
    }
  }

  for (; Q--;) {
    int a, b;
    cin >> a >> b;
    a--; b--;

    if (a == b) {
      puts("0");
      continue;
    }
    if (a > b) swap(a, b);

    int ret = 0;
    for (int i=16; i>=0; i--) {
      if (bk[i][b] > a) {
        ret += 1 << i;
        b = bk[i][b];
      }
    }

    cout << ret + 1 << endl;
  }
}

(DP・バグった)ARC-087-D-FT Robot

問題URL→https://beta.atcoder.jp/contests/arc087/tasks/arc087_b

一位の方のコードをほぼ真似して書いたけど実はそのコードはWAになる可能性のあるコードで、自分で書いたコードは盛大にバグった。

以下が問題のコード。
一位の方は文字列sをchar[]で受け取っていて、それだと通るが、なぜかstringで受け取ると通らない。な~ぜ~。
ツイッターで質問してみたところ原因が判明。
dp[0][0][Z+x]のところでZ+xが-7997になることがあるが、下のコードのコメントアウトしているところのように
char配列を宣言しておくとそのどこかを参照してたまたま通る。
ためしに以下のchar hoge[505050];を追加してみるとこれまた通る。
配列を参照するときインデックスがマイナスの値になってもあらぬところを参照してREになる場合とならない場合があるようだ。
正しくは下駄Zを下のように大きな値にすればオーケー。

配列外参照してないかちゃんとチェックしよう。

  #include <iostream>
  #include <vector>
  #include <string.h>
  #include <stack>
  #include <queue>
  #include <algorithm>
  #include <climits>
  #include <cmath>
  #include <map>
  #include <set>
  #include <assert.h>
  #include <stdio.h>
  #define REP(i,n) for(ll i=0;i<(n);i++)
  #define MOD 1000000007
  #define int long long
  #ifdef int
  const long long INF = LLONG_MAX / 10;
  #else
  const int INF = 1010101010;
  #endif
  using namespace std;
  typedef long long ll;
  typedef vector<vector<ll> > mat;
  typedef pair<int, int> P;
  //typedef pair<double, double> P;
  const int dx[9] = {-1, 0, 0, 1, -1, -1, 1, 1, 0};
  const int dy[9] = {0, -1, 1, 0, -1, 1, -1, 1, 0};
  
  string s;
  int x, y;
  const int Z = 18003;//もとは8003だった
  const int N = 2 * Z + 1;
  bool dp[2][2][N];
  //char hoge[505050];
  // char s[N];

  signed main() {
    cin >> s;
    // scanf("%s", s);
    cin >> x >> y;
    // scanf("%lld%lld", &x, &y);
    int n = s.length();
    // int n = strlen(s);

    dp[0][0][Z] = dp[1][0][Z] = 1;

    int pos = 0LL;
    while (pos < n && s[pos] == 'F') {
      pos++;
      x--;
    }

    int t = 0LL;
    while (pos < n) {
      pos++;
      t ^= 1;
      int L = 0;
      while (pos < n && s[pos] == 'F') {
        pos++;
        L++;
      }
      REP(i,N) dp[t][1][i] = 0; //1の方は計算結果
      REP(i,N) {
        if (!dp[t][0][i]) continue;
        dp[t][1][i-L] = dp[t][1][i+L] = 1;
      }
      REP(i,N) dp[t][0][i] = dp[t][1][i];
    }

    if (dp[0][0][Z+x] && dp[1][0][Z+y]) {
      cout << "Yes" << endl;
    } else {
      cout << "No" << endl;
    }

    return 0;
  }

(残りの文字に変換はmodが変化しない)ARC-094-F-Normalization

問題URL→https://beta.atcoder.jp/contests/arc094/tasks/arc094_d

a,b,cのみの文字列の隣接する異なる2文字を残りの文字に変換する。
ab -> cc
みたいな処理で典型的な考察があるらしい。それは
「aを0,bを1,cを2と考えたときに文字列のその値の総和のmod3は変換前と後で変化しない」
本番中全くその発想に至らなかった。経験が足りない。

解説を見るとどうやら|S|>=4の場合は総和のmod3が等しく同じ文字が連続する箇所が一つでもある文字列は全て作れるらしい。
ただし元の文字列に同じ文字が連続する箇所が1つも無い場合は↑に1を加えた値が答え

kmjpさんのブログのようなDPを実装してみる。

いわゆる配るDP。
ローカル変数modの0初期化を忘れていて無限にバグった。
ローカル変数は初期化を忘れずに!!!

#include <iostream>
#include <vector>
#include <string.h>
#include <stack>
#include <queue>
#include <algorithm>
#include <climits>
#include <cmath>
#include <map>
#include <set>
#include <assert.h>
#include <stdio.h>
#define REP(i,n) for(ll i=0;i<(n);i++)
#define MOD 998244353
#define int long long
#ifdef int
const long long INF = LLONG_MAX / 10;
#else
const int INF = 1010101010;
#endif
using namespace std;
typedef long long ll;
typedef vector<vector<ll> > mat;
typedef pair<int, int> P;
//typedef pair<double, double> P;
const int dx[9] = {-1, 0, 0, 1, -1, -1, 1, 1, 0};
const int dy[9] = {0, -1, 1, 0, -1, 1, -1, 1, 0};
 
string S;
int dp[202020][2][3][3]; 

set<string> se;

void dfs(string ss) {
  se.insert(ss);
  REP(i,ss.length()-1) if (ss[i] != ss[i+1]) {
    string t = ss;
    if ((ss[i] == 'b' && ss[i+1] == 'c') || (ss[i] == 'c' && ss[i+1] == 'b')) t[i] = t[i+1] = 'a';
    else if ((ss[i] == 'a' && ss[i+1] == 'c') || (ss[i] == 'c' && ss[i+1] == 'a')) t[i] = t[i+1] = 'b';
    else if ((ss[i] == 'a' && ss[i+1] == 'b') || (ss[i] == 'b' && ss[i+1] == 'a')) t[i] = t[i+1] = 'c';
    if (se.find(t) == se.end()) {
      dfs(t);
    }
  }
}

int brute(string ss) {
  dfs(ss);
  return se.size();
}

signed main() {
  cin >> S;
  int N = S.length();

  // if (N <= 7) assert(false);

  if (N <= 3) {
    cout << brute(S) % MOD << endl;
    return 0;
  }

  bool same = true;
  REP(i,N-1) if (S[i] != S[i+1]) {
    same = false;
    break;
  }
  if (same) {
    cout << 1 << endl;
    return 0;
  }

  dp[1][0][0][0] = 1;
  dp[1][0][1][1] = 1;
  dp[1][0][2][2] = 1;
  for (int i=1; i<=N-1; i++) {
    REP(C,2) {
      REP(last,3) {
        REP(mod,3) {
          if (dp[i][C][last][mod] != 0) {
            REP(j,3) {
              dp[i+1][C|(last==j)][j][(mod+j)%3] += dp[i][C][last][mod];
              dp[i+1][C|(last==j)][j][(mod+j)%3] %= MOD;
            }
          }
          // REP(j,3) {
          //   dp[i+1][C|(last==j)][j][(mod+j)%3] += dp[i][C][last][mod];
          //   dp[i+1][C|(last==j)][j][(mod+j)%3] %= MOD;
          // }
        }
      }
    }
  }

  int mod = 0;
  REP(i,N) mod += S[i] - 'a';
  mod %= 3;

  int ans = 1;
  ans += dp[N][1][0][mod] + dp[N][1][1][mod] + dp[N][1][2][mod];
  REP(i,N-1) if (S[i] == S[i+1]) {
    ans--;
    break;
  }
  cout << ans % MOD << endl;
}

非負整数を2進数表記に変換するライブラリ

なんか整数をパッと2進数に変換できたら便利だなーと思っていて昔変換する関数とか探したりしたけど
よく考えたら簡単に変換できると気づいた。

#include <iostream>
#include <vector>
#include <string.h>
#include <stack>
#include <queue>
#include <algorithm>
#include <climits>
#include <cmath>
#include <map>
#include <set>
#include <assert.h>
#define REP(i,n) for(ll i=0;i<(n);i++)
#define MOD 1000000007
#define int long long
#ifdef int
const long long INF = LLONG_MAX / 10;
#else
const int INF = 1010101010;
#endif
using namespace std;
typedef long long ll;
typedef vector<vector<ll> > mat;
typedef pair<int, int> P;
//typedef pair<double, double> P;
const int dx[9] = {-1, 0, 0, 1, -1, -1, 1, 1, 0};
const int dy[9] = {0, -1, 1, 0, -1, 1, -1, 1, 0};

string to_bin(ll x, ll keta) {
  string ret = "";
  REP(i,keta) {
    if (x & 1 << i) ret = '1' + ret;
    else ret = '0' + ret;
  }
  return ret;
}

signed main() {
  int N;
  cin >> N;
  cout << to_bin(N, 32) << endl;
}

(xor)ARC-092-D-Two Sequences

問題URL→https://beta.atcoder.jp/contests/arc092/tasks/arc092_b

XORの超教育的問題。XOR苦手なので本番中に解けず・・・

キーポイント
ある非負整数のkビット目(0-indexed)について
2^k=Tとすると
kビット目は
[0,T)なら0
[T,2T)なら1
[2T,3T)なら0
[3T,4T)なら1
になる!!!

1位の人のコードがめっちゃ美しいのでそのまま載せます。
自分で書いたコードは一番下にあります。

#include <bits/stdc++.h>
using namespace std;

int a[200005], b[200005];
int n, ans;

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);
	for (int v = (1<<28);v;v>>=1)
	{
		for (int i = 0;i < n;i++) a[i] &= (v*2-1);
		for (int i = 0;i < n;i++) b[i] &= (v*2-1);
		sort(a, a+n); sort(b, b+n);
		int t = 0;
		for (int i = n-1, j = 0, k = 0, l = 0;i >= 0;i--)
		{
			while (j < n && a[i]+b[j] < v) j++;
			while (k < n && a[i]+b[k] < 2*v) k++;
			while (l < n && a[i]+b[l] < 3*v) l++;
			t += k-j+n-l;
			t &= 1;
		}
		if (t) ans |= v;
	}
	printf("%d\n", ans);
	return 0;
}

ソートされた配列のa以上b未満の個数は
lower_bound(c, c + N, b) – lower_bound(c, c + N, a);
で求められる。

#include <iostream>
#include <vector>
#include <string.h>
#include <stack>
#include <queue>
#include <algorithm>
#include <climits>
#include <cmath>
#include <map>
#include <set>
#include <assert.h>
#include <stdio.h>
#define REP(i,n) for(ll i=0;i<(n);i++)
#define MOD 1000000007
#define int long long
#ifdef int
const long long INF = LLONG_MAX / 10;
#else
const int INF = 1010101010;
#endif
using namespace std;
typedef long long ll;
typedef vector<vector<ll> > mat;
typedef pair<int, int> P;
//typedef pair<double, double> P;
const int dx[9] = {-1, 0, 0, 1, -1, -1, 1, 1, 0};
const int dy[9] = {0, -1, 1, 0, -1, 1, -1, 1, 0};
 
int N;
int a[202020], b[202020];
int c[202020];

string to_bin(ll x, ll keta) {
  string ret = "";
  REP(i,keta) {
    if (x & 1 << i) ret = '1' + ret;
    else ret = '0' + ret;
  }
  return ret;
}

bool check(int x) {
  REP(i,N) c[i] = b[i] % (1 << (x + 1));
  // REP(i,N) cout << to_bin(b[i], 8) << endl;
  // cout << "----------------" << endl;
  // REP(i,N) cout << to_bin(c[i], 8) << endl;
  sort(c, c + N);

  int cnt = 0;
  REP(i,N) {
    int aa = a[i] % (1 << (x + 1));
    int T = 1 << x;
    cnt += lower_bound(c, c + N, 2 * T - aa) - lower_bound(c, c + N, T - aa);
    cnt += lower_bound(c, c + N, 4 * T - aa) - lower_bound(c, c + N, 3 * T - aa);
  }

  return cnt % 2;
}
 
signed main() {
  cin >> N;
  REP(i,N) cin >> a[i];
  REP(i,N) cin >> b[i];

  int ans = 0;
  REP(i,29) if (check(i)) ans |= 1 << i;
  // check(2);
  cout << ans << endl;
}

(gcdの性質)AGC-022-B-GCD Sequence

問題URL→https://beta.atcoder.jp/contests/agc022/tasks/agc022_b

コンテスト中に解けなかった。(残念!)解説を見た。
重要ポイントは\(gcd(a_i, S) = gcd(a_i, S – a_i)\)
この公式初めて見たけどユークリッドの互除法から簡単に導出できる。
ユークリッドの互除法
$$gcd(a, b) = gcd(b, a \% b)$$
この式からaかb一方のもう片方の定数倍は無視できることが分かる。
$$gcd(a, b) = gcd(a, b + ca)$$

また制約を見るとN<=20000で、また作る整数集合の各要素は30000以下なので結構きつい。 また20000という数字から、2の倍数の個数+3の倍数の個数-2と3の倍数の個数が20000なので、そこからエスパーした人もいた。 こういう直感自分もできるようになりたい。 2の倍数と3の倍数だけで構成して和を6の倍数に出来ればいい。 結局コードは1位だった方のを見たけどすごく勉強になった。 うまく和が6の倍数になるように2と3の倍数を加えている。

#include <iostream>
#include <vector>
#include <string.h>
#include <stack>
#include <queue>
#include <algorithm>
#include <climits>
#include <cmath>
#include <map>
#include <set>
#include <assert.h>
#include <numeric>
#define REP(i,n) for(ll i=0;i<(n);i++)
#define MOD 1000000007
#define int long long
#ifdef int
const long long INF = LLONG_MAX / 10;
#else
const int INF = 1010101010;
#endif
using namespace std;
typedef long long ll;
typedef vector<vector<ll> > mat;
typedef pair<int, int> P;
//typedef pair<double, double> P;
const int dx[9] = {-1, 0, 0, 1, -1, -1, 1, 1, 0};
const int dy[9] = {0, -1, 1, 0, -1, 1, -1, 1, 0};
 
signed main() {
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  // cout << sieve(30000) << endl;

  int N;
  cin >> N;

  if (N == 3) {
    cout << “2 5 63″ << endl;
    return 0;
  }

  for (int x=3; x+6<=30000 && N>=4; x+=12, N-=2) {
    cout << x << ” ” << x + 6 << ” “;
  }
  int x = 2;
  for (; N>=3; x+=6, N-=3) {
    cout << x << ” ” << x + 2 << ” ” << x + 4 << ” “;
  }

  if (N == 1) {
    cout << x + 4 << endl;
  } else if (N == 2) {
    cout << x << ” ” << x + 2 << endl;
  }
}