zukaABCをコツコツ解いていきます。
本記事は，管理人の競技プロ精進日記としてログを取ったものです。モチベーションを爆上げするために，積極的にアウトプットしていく作戦です。
これから競技プログラミングを始めようと考えている人や，なんとなく敷居が高いと感じている人の参考になれば嬉しく思います。その他の記事は以下をご覧ください。
目次
本記事の概要
Atcoderで初心者用のコンテストとして開催されているAtcoder Beginner Contest（通称ABC）を解いていくものです。今回はABC173-C「H and V」です。
ポイント
各行と各列が「選ばれるか・選ばれないか」の2通りずつを考えていきます。この表現は2進数と非常に相性がよく，Atcoderでも頻出のアイディアである「bit全探索」を用いて貪欲に解を調べることができます。
今回の問題は，行と列のそれぞれに対してbit全探索を利用する必要があるため，bit全探索をbit全探索でネスト（つまり2重bit全探索）する必要があります。少し頭を捻りますが，結局はbit全探索を2重にしただけなので恐れる必要はありません。
bit全探索については，以下の記事をご覧ください。
あわせて読みたい
【c++で楽しく実装！】bit全探索
本記事では，bit全探索の簡単な解説と実装例をお伝えしていきます。使用言語はc++です。その他の競技プログラミング関連の記事は，以下の目次をご覧ください。 目次へジ...
おさえるべき内容
bit全探索の利用
実装
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repi(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
using namespace std;
typedef long long ll;
char F[10][10];
int main(){
int H, W, K;
cin >> H >> W >> K;
rep(i, H){
rep(j, W){
cin >> F[i][j];
}
}
int ans = 0;
// bit全探索の開始
// 今回は外側のbit全探索はHに設定
rep(bits_H, 1<<H){
// hを選ぶかどうか
bool flag_H[H];
rep(h, H){
// bits_Hに順列の情報が入っている
if (bits_H & (1<<h)) flag_H[h] = true;
else flag_H[h] = false;
}
// 今回は内側のbit全探索はWに設定
rep(bits_W, 1<<W){
// Fを破壊しないようにコピーGを毎回作成する
char G[10][10];
rep(h, H){
rep(w, W){
G[h][w] = F[h][w];
}
}
// wを選ぶかどうか
bool flag_W[W];
rep(w, W){
// bits_Wに順列の情報が入っている
if (bits_W & (1<<w)) flag_W[w] = true;
else flag_W[w] = false;
}
// bitsの情報に応じてコピーしたGを条件通りに書き換えていく
rep(h, H){
if (flag_H[h]==true)
rep(w, W){
G[h][w] = '-';
}
}
rep(w, W){
if (flag_W[w]==true)
rep(h, H){
G[h][w] = '-';
}
}
// #の個数が条件に一致するかどうかを調べる
int check = 0;
rep(h, H){
rep(w, W){
if (G[h][w] == '#') check++;
}
}
// もし条件に合っていればansを1増やす
if (check==K) ans++;
}
}
cout << ans << endl;
}
コメント