【競プロ精進ログ】ABC173-C

zuka

ABCをコツコツ解いていきます。

本記事は,管理人の競技プロ精進日記としてログを取ったものです。モチベーションを爆上げするために,積極的にアウトプットしていく作戦です。

これから競技プログラミングを始めようと考えている人や,なんとなく敷居が高いと感じている人の参考になれば嬉しく思います。その他の記事は以下をご覧ください。

目次

本記事の概要

Atcoderで初心者用のコンテストとして開催されているAtcoder Beginner Contest(通称ABC)を解いていくものです。今回はABC173-C「H and V」です。

ポイント

各行と各列が「選ばれるか・選ばれないか」の2通りずつを考えていきます。この表現は2進数と非常に相性がよく,Atcoderでも頻出のアイディアである「bit全探索」を用いて貪欲に解を調べることができます。

今回の問題は,行と列のそれぞれに対してbit全探索を利用する必要があるため,bit全探索をbit全探索でネスト(つまり2重bit全探索)する必要があります。少し頭を捻りますが,結局はbit全探索を2重にしただけなので恐れる必要はありません。

bit全探索については,以下の記事をご覧ください。

おさえるべき内容

 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;
}
よかったらシェアしてね!

コメント

コメントする

目次
閉じる