ferinの競プロ帳

競プロについてのメモ

SoundHound Inc. Programming Contest 2018 (春) C - 広告

問題ページ
C - 広告

考えたこと

  • ドミノ敷き詰めみたいなbitDPかと思いながら読むと制約的に違う
  • 各連結成分で2部グラフの大きい方を取る気持ちになる→WA
  • よくよく考えると嘘なケースがある
  • 各行ごとに考えると下の行のために看板を置く個数を減らす理由はない気がした(嘘かも)
  • なので各行ごとに置ける最大の個数を置き、その中で下の行に与える悪影響を減らすみたいな貪欲を書いたらWA
    • できるだけ下の行で*のがあるところに看板をおく
    • .の並びを分断して看板が置ける数を減らすようなのを減らす

-----解説を見た-----
二部グラフの最大独立集合なので二部マッチングで求められる

点数メタ読みで解法を捨てたの反省

解法

市松模様に塗れば2次元グリッドで隣り合う頂点の色が異なることから2次元グリッドは2部グラフであるといえる。2部グラフの最大安定集合は頂点数-最大マッチングで求められ、2部マッチングはフローで求められるのでできる。

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define int ll
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef pair<int, int> PII;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define IN(a, b, x) (a<=x&&x<b)
#define PB push_back

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const int MOD = 1000000007;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')';
  return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

string s[45];
int h, w;

#define MAX_V 2000
int V;
VI G[MAX_V];
int match[MAX_V];
bool used[MAX_V];

void add_edge(int u, int v) {
  G[u].PB(v);
  G[v].PB(u);
}

bool dfs(int v) {
  used[v] = true;
  REP(i, G[v].size()) {
    int u = G[v][i], w = match[u];
    if(w < 0 || !used[w] && dfs(w)) {
      match[v] = u;
      match[u] = v;
      return true;
    }
  }
  return false;
}

int bipartite_matching() {
  int res = 0;
  memset(match, -1, sizeof(match));
  REP(v, V) {
    if(match[v] < 0) {
      memset(used, 0, sizeof(used));
      if(dfs(v)) res++;
    }
  }
  return res;
}

int d[45][45];
signed main(void)
{
  cin >> h >> w;
  REP(i, h) cin >> s[i];

  int cnt = 0;
  REP(i, h) REP(j, w) {
    if(s[i][j] == '.') {
      d[i][j] = cnt++;
    }
  }

  REP(i, h) REP(j, w) {
    if(i+1 <= h && s[i][j] == '.' && s[i+1][j] == '.') {
      add_edge(d[i][j], d[i+1][j]);
    }
    if(j+1 <= w && s[i][j] == '.' && s[i][j+1] == '.') {
      add_edge(d[i][j], d[i][j+1]);
    }
    if(s[i][j] == '.') V++;
  }

  cout << V - bipartite_matching() << endl;

  return 0;
}