【Python】行の並べ替えを活用してターゲット行列に一致させるための最小の列反転回数を求めるプログラム

問題の概要

同じ行数・列数を持つ2つの行列、元の行列 M とターゲット行列 T が与えられているとします。使用できる操作は「ある1つの列を選んで反転する」だけで、この操作を行うと、その列内のすべての 1 が 0 に、0 が 1 に変換されます。一方、行の並べ替えは何度でも無料で行えるものとします。この条件下で、行列 M を T と完全に一致させるために必要な最小の操作回数を求めてください。どうしても一致させられない場合は -1 を返します。

たとえば、入力が次のようなケースを考えてみましょう。

M =

T =

このとき出力は 1 になります。まず、行を次のように並べ替えます。

続いて、インデックス 1 の列(右端の列)を反転すると、

となり、行列は T と完全に一致します。

解法のアプローチ

行の並べ替えが自由にできるということは、この問題は本質的に「M の各行を T のどの行に対応付けるか」というマッチング問題だと捉えられます。また、列の反転はすべての行に対して一斉に適用されるため、必要な反転パターンは全行で共通になります。この性質を利用すると、次の手順で解くことができます。

• まず、M と T の各行を2進数のビット列とみなして整数に変換し、それぞれリスト nums1 と nums2 に格納します。こうすることで、行同士の比較や XOR 演算が非常に簡単になります。

• ret := 無限大 として初期化します。

• nums1 の各行 num に対して、以下の処理を実行します。

  • cts := nums1 内の各値とその出現頻度を記録したマップ(Counter)を作成します。

  • cts[num] を 1 減らし、基準となる行自体を対応付けの候補から除外します。

  • my_xor := num XOR nums2[0]。これは「この行をターゲットの先頭行に対応させる場合に必要な列反転パターン」を表します。

  • i を 1 から nums2 のサイズまでループします。

    • needed := my_xor XOR nums2[i]。これはターゲットの i 行目に対応づけられるべき M の行の値です。

    • cts[needed] が 0(存在しない、またはすでに使い切っている)場合は、この対応付けは成立しないためループを抜けます。

    • それ以外の場合は cts[needed] を 1 減らして、その行を使用済みにします。

  • すべての行の対応付けが成功した場合(Python の for-else 構文を利用)、ret := min(ret, my_xor のセットビット数)とします。セットビットの数はそのまま反転すべき列の本数、すなわち操作回数に等しくなります。

• 最後に、ret が無限大のままなら -1 を返し、そうでなければ ret を返します。

計算量について補足すると、行数を n、列数を m とすると、行の整数化に O(nm)、対応付けの検証全体で約 O(n²) の時間がかかり、全体として O(n² + nm) 程度となります。

実装例(Python)

理解を深めるために、以下の実装をご覧ください。

class Solution:
   def solve(self, matrix, target):
      nums1 = []
      nums2 = []
      for row in matrix:
         ths = 0
         while row:
            ths = (ths<<1) + row.pop()
         nums1.append(ths)
      for row in target:
         ths = 0
         while row:
            ths = (ths<<1) + row.pop()
         nums2.append(ths)
      ret=float('inf')
      from collections import Counter
      for num in nums1:
         cts = Counter(nums1)
         cts[num] -= 1
         my_xor = num^nums2[0]
         for i in range(1,len(nums2)):
            needed = my_xor^nums2[i]
            if not cts[needed]:
               break
            cts[needed]-=1
         else:
            ret=min(ret,bin(my_xor).count('1'))
      return ret if ret!=float('inf') else -1
ob = Solution()
M = [
   [0, 0],
   [1, 0],
   [1, 1]
]
T = [
   [0, 1],
   [1, 0],
   [1, 1]
]
print(ob.solve(M,T))

入力

M = [[0, 0],[1, 0],[1, 1]] T = [[0, 1],[1, 0],[1, 1]]

出力

1