ABC173に参加してみた
初めに
ABC173もまたまたAB完でした。大分ぐんにょりな感じですですね。
C問題は全探索のしかたが分からなくて摘んでしました。
なので、またまたC問題について書いていきます。(最近D問題について書いてない気がする、、、)
https://atcoder.jp/contests/abc173
※ブログ内で問題の制約事項をすべて記載はしないので、制約事項は↑のURLより参照願います。
C - H and V
以下のような入力があった場合にちょうど指定された数の黒いマスが残るような塗つぶし方が
いくつあるかを求める問題です。(「.」は白いマス、「#」は黒いマスを表しています。)
塗りつぶし方としては、選択した行または列に含まれるマスをすべて塗りつぶすことができます。
..# ###
解説を見てからの回答
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int main(){
ll H,W,K;
ll ans = 0;
cin >> H >> W >> K;
vector<string> c(H);
for(ll i = 0;i < H;++i) cin >> c[i];
// 列のパターンを2進数で列挙する
// ex. H = 3の場合は1<<3で1000(8)となり000～111(8パターン)まで列挙可能
for(ll h = 0;h < (1<<H);++h) {
// 行のパターンを2進数で列挙する
// ex. W = 4の場合は1<<4で10000(16)となり0000～1111(15パターン)まで列挙可能
for(ll w = 0;w < (1<<W);++w) {
//黒マスの集計用変数
ll count = 0;
//すべてのマスを全探索
for(ll i = 0;i < H;++i){
for(ll j = 0;j < W;++j){
//既に列が塗りつぶされている場合は処理を以降の処理をスキップ
if(h>>i & 1) continue;
//既に行が塗りつぶされている場合は処理を以降の処理をスキップ
if(w>>j & 1) continue;
//塗りつぶされていない黒マスの数をカウント
if(c[i][j] == '#') ++count;
}
}
//黒マスのカウントがKと同様であればansのカウントを増やす
if(count == K) ++ans;
}
}
cout << ans << endl;
return 0;
}
まず、列と行の塗りつぶしパターンの全列挙ですが、bit全探索を利用します。
1の場合は行または列を塗りつぶす、0の場合は行または列を塗りつぶさない
と考えると全パターンの列挙を下記イメージのように行う事ができます。
塗りつぶしのパターンの列挙後に黒マスかどうかを各マス毎に確認していきます。
塗りつぶされた行または列の場合は処理をスキップし、
塗りつぶされていない黒マスだったら数をカウントします。
黒マスの数がKと同様だった場合は、ansのカウントを増やして行くことで、
条件を満たした塗りつぶしパターンがあるかを求めることが出来ます。
最後に
うーん、bit全探索を行えば出来る気はしたんですけどfor文を3重以上で書くことになりそうだなぁ
と思った時点で拒絶反応が出て別な方法が無いかという考えにシフトしちゃったんですよね。。。
(H,Wの入力が最高でも6なので、全然間に合いますが、、、)
前にもbit全探索の問題は解いていたので、解きたかったですね。。。頑張ります。。。
