【ABC173 C】「H and V」を解く【Python3】

「AtCoder」解説一覧へ

H行W列に並ぶマスからなるマス目のうち、選んだ行と列を赤く塗ったとき、残ったマスに黒いマス「#」がK個残るような選び方が何通りあるか求める問題です。

h, w, k = [int(i) for i in input().split()]
mas = [input() for _ in range(h)]

ans = 0

for hi in range(2**h):
    for wi in range(2**w):
        black = 0
        for i in range(h):
            for j in range(w):
                if (hi >> i) & 1 == 0 and (wi >> j) & 1 == 0 and mas[i][j] == '#':
                    black += 1
        if black == k:
            ans += 1
print(ans)

１つの行、列に対して、赤く塗るか否かは2通りでしかないので、すべての選び方を試しても、（H,Wは最大6なので）最大「2¹² = 4096」通りになります。

全パターンを調べても時間は間に合います。

行の選び方は、2^h通り、列の選び方は、2^w通りあります。

二択のものの全パターンを調べる方法として「bit全探索」があります。

「>>」はビットシフト演算子といい、2進数を指定の数だけ右にシフトします。

「<<」は同様に左にシフトします。

x = 13
print(bin(x))                       # > 0b1101
print(x << 1)                       # > 26
print(bin(x << 1))                  # > 0b11010
print(x >> 1)                       # > 6
print(bin(x >> 1))                  # > 0b110

「0b」は2進数の先頭につく文字列です。

「&」は論理積といい、2つの数字の両方が1の場合のみ、1を返します。

x = 7
y = 19
print(bin(x),bin(y))                # > 0b111 0b10011
print(x & y)                        # > 8
print(bin(x & y))                   # > 0b1000

問題に戻ると、

for i in range(h):
    for j in range(w):
        if (hi >> i) & 1 == 0 and (wi >> j) & 1 == 0 and mas[i][j] == '#':
            black += 1

という箇所で、行と列をそれぞれ、i回、j回シフトさせ、1との論理積が0、かつ「#」である場合に、「black」に1を加えています。

すべてのマスを確認し終え、この「black」がKと等しければ、「ans」に1足します。

【ABC173】解説記事リスト

【ABC173 A】「Payment」を解く【Python3】

【ABC173 B】「Judge Status Summary」を解く【Python3】

【ABC173 C】「H and V」を解く【Python3】

「AtCoder」解説一覧に戻る