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

コンテスト一覧へ

 

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)

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

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

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

 

二択のものの全パターンを調べる方法として「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】解説記事リスト

コンテスト一覧に戻る

コメントを残す

メールアドレスが公開されることはありません。