【Python】2値行列の列を反転して、すべての値が等しくなる行の最大数を求める方法

問題の概要

2値行列（各要素が0または1のみで構成される行列）が与えられたとします。この行列に対しては、任意の数の列を選択し、その列に含まれるすべてのセルの値を反転することができます。ここでいう「反転」とは、0を1に、1を0に切り替える操作のことです。このとき、いくつかの列を反転した後、すべての値が等しくなる行の最大数を求めるのがこの問題の目的です。

例として、次のような行列を考えてみましょう。

この場合の出力は 2 になります。最初の2つの列を反転すると、2行目は「1,1,1」、3行目は「0,0,0」となり、これら2行のすべての値が等しくなるためです。

解法のアプローチ

この問題を解くうえでの重要なポイントは、列の反転がすべての行に同時に影響を与えるという点です。つまり、ある行が「すべて同じ値」になるためには、その行と完全に同一の行、またはその行の各ビットを反転させた行（補数）が行列内に存在している必要があります。

具体的な手順は以下の通りです。

• x := 行列、m := 行数、n := 列数、r := 0 として初期化する
• x 内の各行 i について以下を繰り返す：
  • c := 0 とする
  • a := 行 i の全要素 l を反転したリスト（l XOR 1）を作成する
  • x 内の各行 j について、j == i または j == a であれば c を1増やす
• r := c と r の最大値とする
• 最終的に r を返す

実装例

それでは、実際のコードを見てみましょう。

class Solution(object):
   def solve(self, matrix):
      x = matrix
      m = len(matrix)
      n = len(matrix[0])
      r = 0
      for i in x:
         c = 0
         a = [l ^ 1 for l in i]
         for j in x:
            if j == i or j == a:
               c += 1
         r = max(c, r)
      return r

ob = Solution()
matrix = [[0,0,0],
          [0,0,1],
          [1,1,0]]
print(ob.solve(matrix))

入力

[[0,0,0],
[0,0,1],
[1,1,0]]

出力

2

計算量について

このアルゴリズムは、各行について他のすべての行との一致を確認するため、時間計算量は O(m² × n) となります（m は行数、n は列数）。行列のサイズが非常に大きい場合にはパフォーマンスへの配慮が必要ですが、小規模〜中規模の行列であれば十分に実用的なアプローチです。