Python3で解く AtCoder Beginner Contest 173 C - H and V

bit全探索をマス目に対して行う。行と列に対してbit全探索をするのでネストが深くなる。bit演算子に慣れていないとコード自体がよくわからんので、そこらへんもまとめる。さらに、itertoolsでbitの列挙はできるのでそれもやる。

概要

問題

1. のマス目がある。
2. それぞれのマスの色はである。
3. 色は２種類'#'と'.'
4. 今このマスに適当に行と列を選んで（選ばないのもあり）、違う色を塗る。
5. 塗り終えた時に'#'の個数を満たす塗り方は何通りある？

---

解くときに考えた内容

• というところからどの行・列を塗る塗らないを全探索しても程度なので、適当に選んで選ばれたマス目に色をぬって、それから'#'の数を数えれば良さそう
• 結果的にリストの要素の足し算にしたいので読み込み時に'#'をに'.'をに書き換える。
• 塗り直しの色もにしてしまう。

bit全探索について

けんちょんさんが超絶くわしく解説してくれているのでこれを見るのが一番です。はい。

drken1215.hatenablog.com

自分でも多少まとめる。 まずはコードをみながら、とりあえずこんな風にやると3つのbitが立って目的を達成できる。(わかりやすくするためにあえてbitをリストに保存している)

def bit_serch(n):
    for i in range(1 << n):
        a = [0] * n
        for j in range(n):
            if(i >> j) & 1:
                a[j] = 1
        # ここのポイントがbitパターンが2**nのうちの１つが出てくるライン
        print(a)
bit_serch(3)
# [0, 0, 0]
# [1, 0, 0]
# [0, 1, 0]
# [1, 1, 0]
# [0, 0, 1]
# [1, 0, 1]
# [0, 1, 1]
# [1, 1, 1]

でまず、bitのことを知らないと意味がわからないのが

for i in range(1 << n):
# (1 << n)って何？

これは以下のように1のbitを左側にその数だけずらすという意味でbitは2進数なので要するに(1 << n)はという事と同義

bin(1)
'0b1'
bin(1 << 1)
'0b10'
bin(1 << 2)
'0b100'
bin(1 << 3)
'0b1000'

で次が

if(i >> j) & 1:
# (i >> j) & 1って何？

これは10進数化されたiをbitに戻す作業が行われているという事。 例えばi=6の時以下のようになっているので1との論理積をとって1になればその桁に1が立っていたということになる。6という10進数化されたものを元の2進数であるbin(6)つまり、110に戻っている。（0からやると逆順にはなるけど）

bin(6 >> 0)
'0b110'
bin(6 >> 1)
'0b11'
bin(6 >> 2)
'0b1'

(6 >> 0) & 1
0
(6 >> 1) & 1
1
(6 >> 2) & 1
1

これを使って探索するのがbit全探索。

itertoolsを使って塗る塗らないの組み合わせをデカルト積作ってやる方法

筆者はbit演算子に慣れていないのと列挙されていないと考えづらいため、各行・各列共に塗る塗らないを0, 1で表現するリストを作る。例えば以下のようにすると、bitを立てているのと同じ状態になる。ただ列挙するので大量に発生させる際は注意が必要。

list(product([0,1], repeat=2))
# [(0, 0), (0, 1), (1, 0), (1, 1)]

list(product([0,1], repeat=3))
# [(0, 0, 0),
#  (0, 0, 1),
#  (0, 1, 0),
#  (0, 1, 1),
#  (1, 0, 0),
#  (1, 0, 1),
#  (1, 1, 0),
#  (1, 1, 1)]

あとはbit全探索と同じように、塗りきってから全部足し合わせる。コードを見る方が分かる。単純に行・列でに塗る場所を決めたら、その行の列全部を、その列の行全部をとする。

多重リストの平坦化

itertoolsを使わずしてもできるが、せっかくなので利用。以下のようになる。

c = [1, 2, 3], [4, 5, 6]]
print(list(itertools.chain.from_iterable(c)))
# [1, 2, 3, 4, 5, 6]

コード

bit全探索

import copy
import itertools

H, W, K = map(int, input().split())
# あとで足し算で計算するので#は1にそれ以外は0へ
C = [[1 if v == '#' else 0 for v in input()] for _ in range(H)]
ans = 0
# 選んだところは0に塗り直す
for x in range(2**H):
    a = [0] * H
    for y in range(2**W):
        cnt = 0
        c = copy.deepcopy(C)
        for h in range(H):
            if(x >> h) & 1:
                for w in range(W):
                    c[h][w] = 0
        for w in range(W):
            if(y >> w) & 1:
                for h in range(H):
                    c[h][w] = 0
        # flatten
        cnt = sum(list(itertools.chain.from_iterable(c)))
        if cnt == K:
            ans += 1
print(ans)

itertoolsを使って塗る塗らないの組み合わせをデカルト積作ってやる方法

import copy
import itertools
from itertools import product

# itertoolsを使ってパターンを列挙して考える方法
H, W, K = map(int, input().split())
# あとで足し算で計算するので#は1にそれ以外は0へ
C = [[1 if v == '#' else 0 for v in input()] for _ in range(H)]
ans = 0
# 塗り直すか塗り直さないかの01のパターンを出す
HC = list(product([0,1], repeat=H))
WC = list(product([0,1], repeat=W))
# 選んだところは0に塗り直す
c = copy.deepcopy(C)
# hcは塗る行タプル（indexが行目、1だと塗る）
for hc in HC:
    # wcは塗る列タプル（indexが列目、1だと塗る）
    for wc in WC:
        cnt = 0
        # hiが行目
        for hi, h in enumerate(hc):
            if h == 1:
                for w in range(W):
                    c[hi][w] = 0
        # wiが行目
        for wi, w in enumerate(wc):
            if w == 1:
                for h in range(H):
                    c[h][wi] = 0
        # flatten
        cnt = sum(list(itertools.chain.from_iterable(c)))
        if cnt == K:
            ans += 1
        c = copy.deepcopy(C)
print(ans)

---