ABC197 C問題(bit全探索)

C - ORXOR

要約

今回の問題は，まず，グループ分けの方法をすべて考えて，それぞれに対しXORを計算し最小値を求めていく全探索問題です．

区切る方法は，配列の数字の間に仕切り棒を入れるか入れないかの二通りであり，全部で2^(N-1)通りになります．このように入れるかいれないかの２通りを考えていく問題では"bit全探索"という方法が使われます．

また，後半部分のXORを求める部分は，与えられた定義通り実行していくだけです(詳細は画面最下部のコードにコメントを残しています)

■グループ分けの方法

pythonにはbit全探索をするための便利なモジュールが用意されており．

from itertools import product

for bit in product((True, False), repeat=N - 1):

このプログラムを実行すれば，各要素が(True)か(False)かの長さ(N-1)の配列bitが生成されます．

以下にN=3のときの実行例を表示します

(True, True)
(True, False)
(False, True)
(False, False)

これにより，bit[i]がTrueのときは，A[i]とA[i+1]の間に仕切り棒があることを表します．また，このままだと配列Aの一番最後の要素の後ろには仕切り帽がなく後処理が必要になります．これを避けるために，予めbit配列の最後に仕切りを追加しておきます

■区切り方のあるパターンに対してXORの計算

以下のコードでは．

score : あるパターンのときのXORの値

cur : 配列をグループに分けたときの，現在のグループのORの値

ans : XORの最小値

と変数を定義する．

流れとしては各グループのORを計算していき，

仕切りが来るたびに，「scoreを計算して，curを初期化」という流れを繰り返していくだけ．

pythonだと処理時間が間に合わないのでpypyでACした．

N = int(input())
A = list(map(int, input().split()))
ans = float("INF") #最小を考えていくので無限で設定
from itertools import product

for bit in product((True, False), repeat=N - 1):
   #各要素がTrue or False の長さN-1のタプル"bit"を作成できる
   #bit[i]がTrueならA[i]とA[i+1]の間に区切りがあることにする
   bit = list(bit) + [True] #一番最後で終わるため区切り棒を追加しておく
   #print(bit)
   score = 0 #各区間のXOR
   cur = 0 #現区間のOR

   #ある区切り棒のパターンに対して一つのXORを計算する
   for i in range(N):
       cur |= A[i] #ORの計算
       #もし区切り棒があったらscoreを計算して，curを初期化
       if bit[i]:
           score ^= cur
           cur = 0

   ans = min(ans, score) #最小値の更新
print(ans)