ABC197 C 解答

C - ORXOR (809)

問題文

長さ N の数列 A が与えられます。この数列を、1 つ以上の空でない連続した区間に分けます。その後、分けた各区間で、区間内の数のビット単位 OR を計算します。こうして得られた全ての値のビット単位 XOR
として考えられる最小値を求めてください。

制約

1 ≤ N ≤20
0 ≤ A_i < 2^30
入力に含まれる値は全て整数である

考察

まず、演算について簡単に説明します。ORとXORはどちらも2進数にした時の各ビット（桁）に対する演算です。例として1と２と５と見てみます。

１: 0 0 1
2 : 0 1 0
5 : 1 0 1

ORはその名前の通り、どちらかのbitが1であれば1を返す演算です。

1 OR 2 = 001 OR 010 = 011 = 4
2 OR 5 = 010 OR 101 = 111 = 7
1 OR 5= 001 OR 101 = 101 = 5

こんな感じです。 XORは比較する2つの数の該当のビットが等しければ0、異なれば1を返す演算です。もうちょっと言いますと、該当桁の１が偶数個であれば１を奇数個であれば０を返します。

1 XOR 2 = 001 XOR 010 = 011 = 4
2 XOR 5 = 010 XOR 101 = 111 = 7
1 XOR 5 = 001 XOR 101 = 100 = 4

ここで大事なのが、ORやXORの演算はどんな順番で行っても答えが変わらないということです（日本語が難しいですが、ORはOR同士であれば好きな順番でおこなっても良い、ということです、ORとXORを混ぜると答えは変わります。それに応えるのが本問題です）。

ですので、本問題を考える際には、どの組をORで演算するかのグループさえ決めてしまえば、答えはその演算順には依らないため、一意に答えが得られるというわけです。

ということで、どのようにグループ分けするかを考えましょう。これは本問題の制約が

1 ≤ N ≤20

と小さいことを利用します。BIT全探索というやつです。

例を出します。

1 2 3 4 5 6

としましょう。6個の数字がありますね。これをBIT全探索でいくつかのグループに分けます。まずは、6桁の0を用意しましょう。

0 0 0 0 0 0 = 0

これを、全部 1 になるまで全パターン行います。

1 1 1 1 1 1 = 63 

どうやら64パターンあるらしいです。これを使ってグループ分けをします。例えば、

0 0 1 0 1 1 = 11

であれば、連続した数字を同じグループであるとみなすことにより、

[1 2] [3] [4] [56]

とした4グループに分かれます。もう一つ見ましょう。

1 1 1 1 1 0 = 62
[1 2 3 4 5] [6]

ですね。連続の判定は様々なやり方があると思います。私はbitの左シフトを使って、

(1 1 1 1 1 0 & (1 << i) ) *2 == (1 1 1 1 1 0 & (1 << (i+1)))

とやりました。i = 3 としてみましょう。

(1 1 1 1 1 0 & (1 << 3)) * 2
= (1 1 1 1 1 0 & 0 0 1 0 0 0) * 2
= 0 0 1 0 0 0 * 2
= 8 * 2 = 16

(1 1 1 1 1 0 & (1 << (3+1)))
= (1 1 1 1 1 0 & 0 1 0 0 0 0)
= 0 1 0 0 0 0 = 16

です。 *2 はbitを一つ分左に移動する操作に対応します。これが一致していれば、00もしくは11ですので、同じグループに属します。01、10のときは違う値になりますので、グループを変えましょう（0のとき結果は0、1の時には0以外になります）。

グループ分けと書きましたが、実装の際にはどんどん OR 演算をしていき、その結果をある配列に詰め込んでいます。全てのグループ分けが終わった後に、配列にある値を前からXORすることで答えを求めています。

実装も少し大変なのでコメントで補足します。

実装

#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define reps(i,s,n) for(int i=s;i<n;++i)
using namespace std;
using ll = long long;
using P = pair<int, int>;

int main()
{
   int n;
   cin >> n;
   vector<ll> a(n);
   rep(i,n) cin >> a[i];
   //ansには大きな値を入れておく
   ll ans = 1e18;
   //nまでで十分だが、最大ケースにしてある
   rep(i,1<<20)
   {
       ll bit = i;
       //はじめa[0]をいれる
       ll tmp = a[0];
       //グループ分けした数を入れる配列
       vector<ll> v;
       rep(j,n-1)
       {
           //a[1]から開始
           ll bit1 = bit & (1<<j);
           ll bit2 = bit & (1<<(j+1));

           if(bit1*2 == bit2)
           {
               //等しい場合にはORをとる
               tmp = tmp | a[j+1];
           }
           else
           {
               //異なる場合には配列にいれて、仕切り直し
               v.emplace_back(tmp);
               tmp = a[j+1];
           }
       }
       //最後の数も忘れずに入れる
       v.emplace_back(tmp);
       //0のXORは0である（０なら演算に影響を与えない）
       ll now = 0;
       //XOR演算
       for(auto vi:v) now = now ^ vi;
       //最小値であれば更新
       ans = min(ans,now);  
   }
   cout << ans << endl;
   return 0;
}

あとがき

連続する数の判定方法は様々なやり方があると思います。

3 (10) = 11 (2)

なのを利用して、i だけ右シフトして &3 %3 の結果で判定するなんて方法も教えていただきました。賢い。

3を i 個分左シフトして比較する 2 のべき乗（または 0）になっているかで判断するのも良さそうです。

とにかく、連続する数の判定というのが大切なところだったと思います。ですので、この問題はただのBIT全探索よりかはとっても苦戦しました。私はなんとか解くことはできましたが、相当に時間を費やし１WAのおまけもついてきました。

BIT全探索＋αをするという、とても良い問題だったのかなと思います。実際コンテスト中に全探索だと理解してから、「連続部分どうしよう」と考えているときは非常に焦りましたが、楽しかったです。BIT全探索を一応かけるようになった。という方の次のステップにぴったりですね。