[python] JOI予選問題のエラーについて

前提・実現したいこと

JOI予選第7回、5問目（おせんべい）の問題の回答を作成しましたが、5つの入力のうち、1つのみ間違った回答が出力されており、不正解の原因を特定できていません
よろしければ、原因をお教えいただけないでしょうか

発生している問題・エラーメッセージ

上記の入力3に対して正しい出力が得られていない
（正しい出力は2602だが、自分の出力は2592）

該当のソースコード

Python
1def main():
2    r, c  = map(int, input().split())
3    inputlis = []
4    for _ in range(r):
5        inputlis.append(list(map(int, input().split())))
6
7    ans = 0
8        
9    for i in range(2 ** r):
10        cnt = 0
11        for j in range(r):
12            if ((i>>j) & 1):     #0からr-1番目の列をひっくり返すかどうかを0, 1で記述            
13                for x in range(c):  #ひっくり返す列のみ取り出し、全て0/1を入れ替える
14                    if inputlis[j][x] == 0:
15                        inputlis[j][x] = 1
16                    else:
17                        inputlis[j][x] = 0
18
19        for m in range(c):      #ひっくり返したのち、m列目の表（"1"）を数える。0の方が多い場合、この列を裏返す（max(tmp, r-tmp)がこの動作に当たる）
20            tmp = 0
21            for retsu in inputlis:
22                tmp += retsu[m]
23            cnt += max(tmp, r - tmp)
24
25        if cnt > ans:
26            ans = cnt
27    print(ans)
28
29
30if __name__ == "__main__":
31    main()

試したこと

各入出力は試しており、入力1-2, 4-5は正解になっています
入力3については正解者のソースコードと照らし合わせたりしたのですが、恐縮ですが不正解になる原因がわかっておりません

補足情報（FW/ツールのバージョンなど）

手元でのcommand prompt上、ネット上の判定いずれも試しています

行動規範の内容に同意します

回答1件

ベストアンサー

おせんべいを裏返した後、元に戻していないからパタン漏れが発生しているのではないでしょうか。
以下のようにcntを計算した後におせんべいを元に戻すコードを追加したところ、答えは2602になりました。
(ただし、このコードだとR=10, C=10,000のようなデータだと時間がかかりすぎると思います)

def main():
    r, c  = map(int, input().split())
    inputlis = []
    for _ in range(r):
        inputlis.append(list(map(int, input().split())))

    ans = 0

    for i in range(2 ** r):
        cnt = 0
        for j in range(r):
            if ((i>>j) & 1):     #0からr-1番目の列をひっくり返すかどうかを0, 1で記述
                for x in range(c):  #ひっくり返す列のみ取り出し、全て0/1を入れ替える
                    if inputlis[j][x] == 0:
                        inputlis[j][x] = 1
                    else:
                        inputlis[j][x] = 0

        for m in range(c):      #ひっくり返したのち、m列目の表（"1"）を数える。0の方が多い場合、この列を裏返す（max(tmp, r-tmp)がこの動作に当たる）
            tmp = 0
            for retsu in inputlis:
                tmp += retsu[m]
            cnt += max(tmp, r - tmp)

        if cnt > ans:
            ans = cnt

        ### コピペで追加
        for j in range(r):
            if ((i>>j) & 1):     #0からr-1番目の列をひっくり返すかどうかを0, 1で記述
                for x in range(c):  #ひっくり返す列のみ取り出し、全て0/1を入れ替える
                    if inputlis[j][x] == 0:
                        inputlis[j][x] = 1
                    else:
                        inputlis[j][x] = 0
        ###
    print(ans)

投稿2020/05/06 04:49