Pythonで各行要素を反転して最大合計を見つけるプログラム

2Dバイナリ行列があるとします。指定された行列の任意の行または列について、すべてのビットを反転できます。これらの操作をいくつでも実行でき、各行を2進数として扱う場合は、これらの数値で作成できる最大の合計を見つける必要があります。

したがって、入力が次のような場合

その場合、出力は11になり、両方の行を反転すると101と110が得られ、合計は5 + 6=11になります

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

• 行列の各行rについて、次のようにします
  • r [0]が0と同じ場合、
    • 0からrのサイズの範囲のiについては、
      • r [i]：=-r [i] + 1
• 1から行列の列サイズまでの範囲のjについては、
  • cnt：=0
  • 行列の行数が0から行数の範囲のiについては、
    • cnt：=cnt + 1（matrix [i、j]が1の場合）それ以外の場合は-1
  • cnt <0の場合、
    • 行列の0から行サイズの範囲のiの場合、
      • matrix [i、j]：=-matrix [i、j] + 1
• ans：=0
• 行列の各行rについて、次のようにします
  • a：=0
  • rのvごとに、
    • a：=2 * a + v
  • ans：=ans + a
• 回答を返す

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

例

class Solution:
   def solve(self, matrix):
      for r in matrix:
         if r[0] == 0:
            for i in range(len(r)):
               r[i] = -r[i] + 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
      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