PythonですべてのセグメントのXORをゼロに等しくするプログラム

numsという配列と別の値kがあるとします。セグメント[左、右]（左<=右）のXORは、インデックスが左と右（両端を含む）の間にあるすべての要素のXORです。

サイズkのすべてのセグメントのXORがゼロと同じになるように、配列内で変更する要素の最小数を見つける必要があります。

したがって、入力がnums =[3,4,5,2,1,7,3,4,7]、k =3のような場合、インデックス2、3の要素を変更できるため、出力は3になります。 4を使用して、配列[3,4,7,3,4,7,3,4,7]を作成します。

これを解決するには、次の手順に従います-

• 制限：=1024

• temp：=サイズがLIMIT x kの配列を作成し、0で埋めます

• インデックスiと値x（nums）ごとに、実行します

  • temp [i mod k、x]：=temp [i mod k、x] + 1

• dp：=サイズLIMITの配列で、-2000で埋める

• dp [0]：=0

• 一時的な行ごとに、実行します

  • maxprev：=最大dp

  • new_dp：=サイズLIMITの配列でmaxprevで埋める

  • インデックスiと値cntの行ごとに、次のようにします

    • cnt> 0の場合、

      • dpの各インデックスjと値prevについて、実行します

        • new_dp [i XOR j]：=new_dp [iXORj]およびprev+cnt

          の最大値

  • dp：=new_dp

• numsの戻り値-new_dp[0]

例

理解を深めるために、次の実装を見てみましょう

def solve(nums, k):
   LIMIT = 2**10
   temp = [[0 for _ in range(LIMIT)] for _ in range(k)]
   for i,x in enumerate(nums):
      temp[i%k][x] += 1

   dp = [-2000 for _ in range(LIMIT)]
   dp[0] = 0
   for row in temp:
      maxprev = max(dp)
      new_dp = [maxprev for _ in range(LIMIT)]
      for i,cnt in enumerate(row):
         if cnt > 0:
            for j,prev in enumerate(dp):
               new_dp[i^j] = max(new_dp[i^j], prev+cnt)
         dp = new_dp
   return len(nums) - new_dp[0]

nums = [3,4,5,2,1,7,3,4,7]
k = 3
print(solve(nums, k))

入力

[3,4,5,2,1,7,3,4,7], 3

出力

-9