2進数の扱い方　おせんべいの問題 - 競技プログラミング悪戦苦闘日記

今回はビット全探索を使いつつ2進数で操作する問題を解きました。
2進数の扱いについて、いくつかポイントを書きます。

問題をざっくりいうと、せんべいを表と裏を焼かないといけなくて、
表面を焼いてる途中で地震が起きて、何枚か裏返ったんだけど、まだ裏返ってないのがあるから、
行か列でせんべいをひっくり返して、最大で何枚のせんべいを裏面にして出荷できるか。

問題文が長いのもあるのですが、この問題のルールを理解するのに10分以上かかりました。。。
私の読解力に問題があるとは思うけど、慣れればすんなり理解できるのでしょうか。。。

方針としては、問題文でヒントがあるように、行数は最大で10というところに着目して、
行をひっくり返すパターンはビット全探索します。
せいぜい、 $2^{10} = 1024$ 通り

どの列をひっくり返すかは、列を見て、表が多ければひっくり返します。
問題で問われているのは、操作をした後の裏面を焼いている枚数なので、
列で探索して表面と裏面の数で、多い数を足しあげていきます。

ひっくり返す操作はXOR（排他的論理和）を使う

たまたまzobrist hashingを知識として知っていたので、すんなり気づけました。
XORは値が等しいときはFalse、値が異なるときはTrueになります。
なので1をXORしてあげれば、0 XOR 1 -> 1になりますし、1 XOR 1 -> 0になります。

formatで10進数から2進数へ変換

format関数で10進数から2進数へ変換しました。
変換するときに行の数が最大で10なので、10桁になるようにしています。

# bitは整数が入ります。ビット全探索で使用するbit。
format(bit, '010b')

結局一番苦労したのは列単位で探索するところでした。
例えば3行4列の問題で、ビットが0000000110のとき、1行目と2行目をひっくり返すつもりなのですが、
その時に1行目のk列目をどうやってひろってきて、XORしたら良いかかなり悩み、不具合などもあって1時間以上苦労しました。。。

結局は涙ぐましい努力で乗り切りました。

int(flip_row_pos[10 - R + k])

以下は全文です。

R, C = list(map(int, input().split()))
senbei_pos = []
ans = 0
for _ in range(R):
    pos = list(map(int, input().split()))
    senbei_pos.append(pos)

for bit in range(2**R):
    total = 0
    copied_pos = senbei_pos[:]
    # Rの上限が10なので10桁の2進数になるように0で埋める
    flip_row_pos = list(format(bit, '010b'))
    for j in range(C):
        column = [p[j] for p in copied_pos]
        one_count = sum([column[k] ^ int(flip_row_pos[10 - R + k])
                         for k in range(R)])
        zero_count = R - one_count
        total += max(zero_count, one_count)
    ans = max(ans, total)
print(ans)