AtCoder Beginner Contest 173を見直す / C - H and V

問題

C - H and V

白か黒で塗られたH行W列の表が与えられるので、任意の列と行を赤く塗った際に、黒いマスの数がK個になるパターンの数を答える問題

制約
1<=H,W<=6

解答

2^12の全検索問題だと言うことはすぐに分かったんですが、いい感じに実装できなかった。色々ゴチャゴチャやって解いたのが以下

import itertools
import copy
H, W, K = map(int, input().split())
C = []
for _ in range(H):
   C.append([c for c in input()])

H_list = [i for i in range(H)]
H_comb = []
for i in range(1, H):
   H_comb += itertools.combinations(H_list, i)

W_list = [i for i in range(W)]
W_comb = []
for i in range(1, W):
   W_comb += itertools.combinations(W_list, i)

ans = 0
cnt = 0
for w in C: cnt += w.count('#')
if cnt == K: ans += 1

for wc in W_comb:
   temp_C0 = copy.deepcopy(C)
   for i in sorted(wc, reverse=True):
       for w in temp_C0: w.pop(i)
   cnt = 0
   for w in temp_C0 : cnt += w.count('#')
   if cnt == K: ans += 1

for hc in H_comb:
   temp_C1 = copy.deepcopy(C)
   for i in sorted(hc, reverse=True): temp_C1.pop(i)
   cnt = 0
   for w in temp_C1: cnt += w.count('#')
   if cnt == K: ans += 1
   for wc in W_comb:
       temp_C2 = copy.deepcopy(temp_C1)
       for j in sorted(wc, reverse=True):
           for w in temp_C2: w.pop(j)
       cnt = 0
       for w in temp_C2 : cnt += w.count('#')
       if cnt == K: ans += 1
print(ans)

Pythonの「itertools」で、全パターンを出して、コピーしたリストにパターンを適応して数を数え上げてます。どう見ても判りづらいので解説動画を見て作った回答が以下。

H, W, K = map(int, input().split())
C = []
for _ in range(H): C.append([c for c in input()])
ans = 0
for i in range(1<<H):
   for j in range(1<<W):
       cnt = 0
       for m in range(H):
           for n in range(W):
               if i>>m&1: continue
               if j>>n&1: continue
               if C[m][n] == '#': cnt += 1
       if cnt == K: ans += 1
print(ans)

bit全検索と言う方法を使って解答しています。この問題の場合、赤く塗るか塗らないかの２パターンの状態を二進数で「1」は「赤く塗られた状態」、「0」は「元の色のまま」を表して処理しています。bit全検索の肝となっているのは以下の二点です。

1<<H
 -> 2^H
i>>m&1
->iをmだけビットシフトして1と&演算することによって、iを二進数表記した際のm桁目の値を出力しています。

ちなみにC++だと以下のようになります。

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
using ll = long long;
using P = pair<int, int>;

int main() {
   int H, W, K;
   cin >> H >> W >> K;
   vector<string> C(H);
   rep(i, H) cin >> C.at(i);
   int ans = 0;
   rep(i, 1<<H) rep(j, 1<<W) {
       int cnt = 0;
       rep(m, H) rep(n, W){
           if(i>>m&1) continue;
           if(j>>n&1) continue;
           if(C[m][n] == '#') cnt++;
       }
       if (cnt == K) ans++;
   }
   cout << ans << endl;
}

ちなみにこの問題再帰関数を利用した木構造でも解けるらしいので、余裕があれば試してみたい。

前回