ABC197C - ORXORをビット全探索で解いてみた

40代文系社内SEが、AtCoder Beginner Contest 197 C - ORXORをCommon Lispで解いてみました。

まず問題文を見ます。
数列$A$をいくつかのグループに分け、グループ内で$\mathrm{OR}$を計算します。さらに、得られた値の$\mathrm{OR}$を計算します。
グループの分け方によって$\mathrm{XOR}$で得られる値が変わるので、その最小値を求める問題です。
等しい値の$\mathrm{XOR}$は0になるので、すべてのグループが同じ値になれば最小になりますが、できるだけ小さくする方法はちょっと見当もつきません。

次に制約を見ます。
$N$の最大値が20となっているので、ビット全探索なら$2^{20}=1048576$なので使えるかもしれません。
ビット全探索で解くとすると、何をビットで表現するかが問題になります。
ここで私が思いついたのは、壁をビットで表現する方法です。
数列$A$をグループ化するという部分を、数の間に壁を置くと読み替え、置く/置かないをビットで表現する方法です。
壁の設置数は、最大で$N-1$になります。

例えば入力例1であれば、

• $(0)_{10}=(00)_2$のとき、壁を置かずに全体を1つのグループとする
• $(1)_{10}=(01)_2$のとき、5と7の間に壁を置き、1,5と7に分ける
• $(2)_{10}=(10)_2$のとき、1と5の間に壁を置き、1と5,7に分ける
• $(3)_{10}=(11)_2$のとき、各数の間に壁を置き、すべて別のグループとする

$(2)_{10}=(10)_2$のときのイメージを以下に示します。

計算量はビット全探索の$2^N$と、それぞれのパターンでORXORの計算する$N$で全体で$O(2^N \times N)$となり、最大$20971520$で、間に合いそうです。

(let* ((n (read))
       (a (make-array n)))

  (loop for i from 0 below n
        do (setf (aref a i) (read)))

  (loop for b from 0 below (expt 2 (1- n))
        for ors = (loop with temp-ors = nil
                        with temp-or = 0
                        for i from 0 below n
                        do (setf temp-or (logior temp-or (aref a i)))
                           (when (or (= i (1- n))
                                     (logbitp i b))
                             (push temp-or temp-ors)
                             (setf temp-or 0))
                        finally
                           (return temp-ors))
        minimize (reduce #'logxor ors)
          into it
        finally
           (format t "~A~%" it)))
  

制約からアルゴリズムを推測し、問題を解くことができました。

AtCoder Beginner Contestを解いてみたリスト