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

0と1だけで構成される行列があるとします。この行列では、任意の数の列を選び、その列に含まれるすべてのセルを反転（フリップ）することができます。セルの反転とは、そのセルの値を0から1へ、あるいは1から0へ変更することを意味します。ここで、いくつかの列を反転した後に「すべての値が等しい行」となり得る行の最大数を求める必要があります。

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

この場合の出力は 2 になります。最初の2つの列の値を反転すると、2行目と3行目がそれぞれ同じパターンになり、値が一致するためです。

ポイントとなる考え方

重要なのは、列単位での反転は「行同士の各位置の値が同じか異なるか」という対応関係を壊さないという点です。つまり、ある行に対して、完全に一致する行と各要素が反転された（補となる）行だけが、適切な列の反転によって同じパターンに揃えられます。したがって、各行について「自分自身と一致する行」と「補となる行」の合計数を数え、その最大値を答えとすればよいのです。

解法の手順

• x := 行列、m := 行数、n := 列数、r := 0 とする
• x の各行 i について以下を実行する
  • c := 0 と初期化する
  • a := i の各要素 l を反転した値（l XOR 1）からなるリストを作成する
  • x の各行 j について、j == i または j == a であれば c を 1 増やす
• r := max(c, r) として最大値を更新する
• 最後に r を返す

それでは、理解を深めるために実際の実装例を見てみましょう。

実装例

class Solution(object):
    def maxEqualRowsAfterFlips(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()
print(ob.maxEqualRowsAfterFlips([[0,0,0],[0,0,1],[1,1,0]]))

入力

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

出力

2

計算量と改善のヒント

この解法では各行ごとに行列全体を再度走査するため、時間計算量は O(m² × n)（m は行数、n は列数）となります。入力サイズが大きい場合は、各行をタプル化し、「元の行」と「反転した行」のうち代表となる方をキーとして Counter で出現回数を数える方法が有効です。このアプローチなら O(m × n) まで高速化でき、コードもより簡潔になります。