Pythonで行・列のビット反転により2進行列の最大合計を求めるプログラム

問題概要

2次元のバイナリ行列（各要素が0または1の行列）が与えられます。任意の行または列を選び、そのすべてのビットを反転（0を1に、1を0に変更）する操作を何度でも実行できます。各行を2進数として読み取ったとき、これらの数値の合計を最大化するには、どのように操作すべきでしょうか。

具体例

たとえば、次のような行列が入力されたとします。

この場合の出力は 11 になります。2つの行をそれぞれ反転すると「101」と「110」になり、10進数では 5 + 6 = 11 となるためです。

解法の考え方（貪欲法）

合計を最大化する鍵は、大きい桁のビットを優先的に1にすることです。以下の2つの戦略を組み合わせます。

• 最上位ビットは必ず1にする： 各行の先頭ビットが最も大きな桁の重みを持つため、先頭が0になっている行は必ず反転します。
• 残りの列は多数決で判断する： 各列について1の数と0の数を比較し、0の方が多い列は全体を反転して1を増やします。

具体的には、次の手順で処理を進めます。

1. 行列内の各行 r について、先頭要素 r[0] が 0 なら、その行全体のビットを反転します。
2. 2列目以降の各列 j について、カウンタ cnt を用意し、matrix[i][j] が 1 なら +1、0 なら −1 として全行分を合計します。cnt が負になった場合（0が過半数の場合）は、その列全体のビットを反転します。
3. 各行を左から右へ「a = 2 × a + v」の式で2進数として変換し、その値を答え ans に加算していきます。
4. 最後に ans を返します。

Pythonでの実装例

class Solution:
   def solve(self, matrix):
      # 各行の先頭ビットを必ず1にする
      for r in matrix:
         if r[0] == 0:
            for i in range(len(r)):
               r[i] = -r[i] + 1

      # 先頭以外の各列で、1の数が多くなるよう調整する
      for j in range(1, len(matrix[0])):
         cnt = 0
         for i in range(len(matrix)):
            cnt += 1 if matrix[i][j] else -1
         if cnt < 0:
            for i in range(len(matrix)):
               matrix[i][j] = -matrix[i][j] + 1

      # 各行を2進数として評価し、合計を求める
      ans = 0
      for r in matrix:
         a = 0
         for v in r:
            a = 2 * a + v
         ans += a
      return ans

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

入力

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

出力

11

計算量の目安

行数を R、列数を C とすると、すべての行と列を一度ずつ走査するため時間計算量は O(R×C) です。また、入力行列をそのまま書き換える実装であれば追加のメモリが不要となり、空間計算量は O(1) に抑えられます。

まとめ

この問題は、「上位の桁ほど価値が高い」という2進数の性質を利用した貪欲法の典型例です。各行の先頭ビットを強制的に1にし、それ以外の列については多数決で反転の要否を判断するだけで、常に最大の合計を得ることができます。シンプルなループ処理だけで実装できるため、ビット操作や二次元配列の操作を学ぶ練習題材としても最適です。