JOI難易度６おせんべい - あっとのTECH LOG

問題原文

問題要旨

$H$ × $W$ のグリッドがあり、各セルは １ か ０ かである。
ある行を好きなだけ選び、その行の１と０を反転 → ある列を好きなだけ選び、その列の１と０を反転という操作を１回行う。
操作後のグリッド上の０と書かれたセルの数を最大化せよ。

$1 \leq H \leq 10$
$1 \leq W \leq 1000$
実行時間制限 10sec

解法

行についての制約が小さいので、行の選び方を全探索する。

すると各列について、

１の数が多い → 反転するほうがよい
０の数が多い → 反転しないほうがよい

という状態になる。あとは０の数が最大になるように、各列について計算を行えばよい。

行の選び方を全探索 → $O(2^{H})$
各列について、行の操作後にいくつ０になっているかを計算 → $O(HW)$

なので、計算量は $O(2^{H}HW)$ になる。
実行時間制限が相当に緩いので余裕で間に合う。

実装

itertools.product を使うと楽。

from itertools import product
R, C = map(int, input().split())
G = [list(map(int, input().split())) for _ in range(R)]

ans = 0
for pattern in product([0, 1], repeat=R):
    tmp_ans = 0
    reverse_tips = [0] * C
    for r in range(R):
        for c in range(C):
            if pattern[r] == G[r][c]:
                reverse_tips[c] += 1

    for rc in reverse_tips:
        tmp_ans += max(rc, R - rc)

    ans = max(ans, tmp_ans)

print(ans)

感想

特徴的な制約に注目、というのは基本ですね。