概要

\(H \times W\) のグリッドから、いくつかの「行」と「列」を自由に選び、それらに含まれるマスの値の合計 \(S\) を最大化する問題です。

考察

補色の考え方（余事象の利用）

選んだ行の集合を \(R\)、列の集合を \(C\) とします。塗りつぶされるマスは「行 \(i \in R\) または 列 \(j \in C\)」に属するマスです。 この合計 \(S\) を直接最大化するのは少し複雑ですが、「塗りつぶされないマス」に注目すると見通しが良くなります。

塗りつぶされないマスは、「行 \(i \notin R\) かつ 列 \(j \notin C\)」を満たすマス、つまり \(R\) にも \(C\) にも選ばれなかった行と列の交差部分にあるマスです。 選ばなかった行の集合を \(R'\)、選ばなかった列の集合を \(C'\) とすると、全マスの合計を \(\text{TotalSum}\) として、 $\(S = \text{TotalSum} - \sum_{i \in R'} \sum_{j \in C'} A_{i,j}\)\( と表せます。\)S\( を最大化するには、引き算の項である **\)f(R’, C’) = \sum{i \in R’} \sum{j \in C’} A_{i,j}$ を最小化**すればよいことになります。

列の選択の最適化

ある行の集合 \(R'\) を固定したとき、どの列を \(C'\) に入れるべきかを考えます。 \(B_j = \sum_{i \in R'} A_{i,j}\) を「集合 \(R'\) に含まれる行における、列 \(j\) の値の合計」とすると、 $\(f(R', C') = \sum_{j \in C'} B_j\)\( となります。この値を最小にするには、**\)B_j\( が負であるような列 \)j\( をすべて \)C’\( に選べばよい**ことがわかります（\)Bj \geq 0\( なら選ばない方が和は小さくなりません）。 したがって、固定された \)R’\( に対して最小の \)f\( は \)\sum{j=1}^{W} \min(0, B_j)$ となります。

計算量の削減

行の選び方 \(R'\) は \(2^H\) 通りあります。各 \(R'\) に対して \(B_j\) を一から計算すると \(O(2^H \cdot HW)\) かかり、制約（\(H, W \leq 19\)）では Python だと実行時間制限が厳しくなります。

そこで、グレイコード (Gray Code) を利用します。グレイコードを用いると、部分集合を走査する際に「直前の状態から要素を 1 つ追加または削除する」だけで次の状態に遷移できます。 これにより、各ステップで \(B_j\) の更新を \(O(W)\) で行えるため、全体の計算量を \(O(2^H \cdot W)\) に削減できます。

アルゴリズム

1. グリッドの全マスの合計 total_sum を計算する。
2. 計算量を抑えるため、\(H > W\) の場合は行列を転置し、\(H \le W\) となるようにする。
3. グレイコードを用いて、行のすべての部分集合 \(R'\) を順に走査する。
   • 直前の \(R'\) から行 \(k\) が追加（または削除）された場合、各列 \(j\) について \(B_j\) に \(A_{k,j}\) を加算（または減算）する。
   • 同時に、\(\sum \min(0, B_j)\) の値を差分更新で管理する。
4. すべての \(R'\) の中で、\(\sum \min(0, B_j)\) の最小値 min_f を求める。
5. total_sum - min_f が答えとなる。

計算量

• 時間計算量: \(O(2^{\min(H, W)} \cdot \max(H, W))\)
  • 行と列のうち小さい方を指数部（\(2^{19} \approx 5.2 \times 10^5\)）に持ってくることで、約 \(10^7\) 回程度の演算に収まります。
• 空間計算量: \(O(HW)\)
  • グリッドの値を保持するメモリが必要です。

実装のポイント

• 転置の処理: \(H > W\) のときに行列を入れ替えることで、常に \(2^{19} \times 19\) 程度のループ回数を保証できます。

• グレイコードの遷移: i ^ (i >> 1) を使う方法もありますが、今回のコードのように「変化するビット k = (i & -i).bit_length() - 1」を特定して、そのビットに対応する行を足し引きする方法が効率的です。

• 差分更新: B[j] の値が変わる際、その値が負である場合のみ合計に寄与するように curr_f を更新することで、内側のループを高速化しています。

  ソースコード

import sys

def solve():
    # Set up input reading
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # Read grid dimensions
    H = int(input_data[0])
    W = int(input_data[1])
    
    # Read grid values
    A = []
    idx = 2
    for i in range(H):
        A.append([int(x) for x in input_data[idx : idx + W]])
        idx += W

    # To optimize the complexity O(2^H * W), we ensure H is the smaller dimension.
    # If H > W, we transpose the grid.
    if H > W:
        A = [[A[i][j] for i in range(H)] for j in range(W)]
        H, W = W, H

    # Calculate the total sum of all values in the grid.
    total_sum = 0
    for row in A:
        for x in row:
            total_sum += x
    
    # Pre-calculate row references for faster access in the loop.
    A_rows = [row for row in A]
    
    # B[j] will store the sum of values in column j for the current subset of rows R'.
    B = [0] * W
    
    # curr_f will store the sum of negative values in B, i.e., sum(min(0, B[j])).
    # This represents the minimum sum we can get from choosing columns C' for a fixed R'.
    curr_f = 0
    
    # min_f will store the minimum value of curr_f found across all row subsets R'.
    min_f = 0
    
    # g will track the current Gray code value.
    g = 0
    
    # num_subsets is 2^H.
    num_subsets = 1 << H
    
    # We iterate through all subsets of rows using a Gray code sequence.
    # Gray code ensures that exactly one row is added or removed at each step,
    # allowing us to update the column sums B[j] and the value curr_f incrementally.
    for i in range(1, num_subsets):
        # k is the index of the bit that changes in the Gray code.
        # (i & -i).bit_length() - 1 finds the position of the rightmost set bit in i.
        k = (i & -i).bit_length() - 1
        row_k = A_rows[k]
        g ^= (1 << k)
        
        if g & (1 << k):
            # The k-th bit of g changed from 0 to 1, so we add row k.
            for j, rkj in enumerate(row_k):
                obj = B[j]
                nbj = obj + rkj
                # Update curr_f based on the change from obj to nbj.
                if nbj < 0:
                    curr_f += nbj
                if obj < 0:
                    curr_f -= obj
                B[j] = nbj
        else:
            # The k-th bit of g changed from 1 to 0, so we remove row k.
            for j, rkj in enumerate(row_k):
                obj = B[j]
                nbj = obj - rkj
                # Update curr_f based on the change from obj to nbj.
                if nbj < 0:
                    curr_f += nbj
                if obj < 0:
                    curr_f -= obj
                B[j] = nbj
        
        # Track the minimum f(R', C') across all subsets.
        if curr_f < min_f:
            min_f = curr_f
    
    # The maximum sum S is TotalSum - min(f(R', C')), where f(R', C') is the sum
    # of elements in the intersection of rows R' and columns C'.
    # This is derived from the complement of the filled cells.
    print(total_sum - min_f)

if __name__ == '__main__':
    solve()

この解説は gemini-3-flash-thinking によって生成されました。