目的

Atcoderで上を目指すべく、「競プロ初中級者100問」を解いている中でpythonの仕様で面白い問題に直面したので共有する
- 言語はpython3系(pypy7.3 or python3.8.5)を利用している

qiita.com

問題

要約: おせんべいの表を0, 裏を1とした際に、与えられた行列R(最大10) × C(最大10000)の行列の表の数を最大化する
- JOI = 日本情報オリンピック

atcoder.jp

ポイント

計算量に関して

単純な全探索でなく、問題の条件/性質より探索範囲を絞り込む必要がある

全ての数を探索した場合 2^R * 2^Cとなり、全部の組み合わせを求めることは不可能(O(2^R+C))
- ちなみに、「2¹⁰⁰⁰⁰⁰ ≒ 9.99 * 10³⁰¹⁰²」通りという回数を全探索することになる
そのため、Rに関して全探索したのちに、その場合に関して、Cの探索を行う(O(2^RRC))
- ちなみに、「2 ^ 10 * 10 * 10000 = 1.024 * 10⁸」となり、何とか完了することができる
公式の解説通りに解いたと思われる

www.ioi-jp.org

実装

行に関してbit全探索を行い、その上で各列に関して数え上げ、ひっくり返すかどうか考える
- 各列に関して数え上げ、その列における値において1が多ければひっくり返す、そうでなければそのままとする

R, C = map(int, input().split())
S = [list(map(int, input().split())) for _ in range(R)]

ans = 0
range_r, range_c = range(R), range(C)
S_ini = [[0] * C for _ in range_r]


for i in range(2 ** R):
    bit = bin(i)[2:].rjust(R, "0")
    s = 0
    S_copy = S_ini
    for j, b in enumerate(list(bit)):
        if b == "1":
            sj = S[j]
            S_copy[j] = list(map(lambda x: (x+1) % 2, sj))
        else:
            S_copy[j] = S[j]

    for c in range_c:
        cnt = 0
        for r in range_r:
            if S_copy[r][c] == 1:
                cnt += 1
        s += max(cnt, R-cnt)
    ans = max(ans, s)

print(ans)

ちなみに、pypyでなくpython3で実行した場合はTLEになる(11s以上でTLEに・・・)
- ref: https://atcoder.jp/contests/joi2008yo/submissions/20424945

実行結果

何とかACすることができた(2秒以上かかっているので非常に遅い・・・orz)
- ref: https://atcoder.jp/contests/joi2008yo/submissions/20426131

気になったポイント

最初に、標準ライブラリのdeepcopyを利用し解いたが、非常に時間がかかった

from copy import deepcopy

R, C = map(int, input().split())
S = [list(map(int, input().split())) for _ in range(R)]

ans = 0
range_r, range_c = range(R), range(C)

for i in range(2 ** R):
    bit = bin(i)[2:].rjust(R, "0")
    s = 0
    S_copy = deepcopy(S)

    for j, b in enumerate(list(bit)):
        if b == "1":
            sj = S_copy[j]
            S_copy[j] = list(map(lambda x: (x+1) % 2, sj))

    for c in range_c:
        cnt = 0
        for r in range_r:
            if S_copy[r][c] == 1:
                cnt += 1
        s += max(cnt, R-cnt)
    ans = max(ans, s)

print(ans)

おせんべいのinputを保持するSをdeepcopyを利用して計算した場合、非常に時間かかる(10s近くかかるが、宣言時間がザルのためACできるww)
- deepcopyはpython仕様上遅いようである
  - ref: https://atcoder.jp/contests/joi2008yo/submissions/20424725

qiita.com