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

問題文

atcoder.jp

概要

'.'と'#'からなるグリッドが与えられる。 以下のルールの元で出来るだけ多くの'.'を選択する時、選んだ'.'の個数を出力する。

• 隣り合う'.'の両方を選ぶことはできない

解法

まずグリッドをグラフとみなすと、二部グラフの最大独立集合のサイズを出力すればいいことがわかります。

最大独立（安定）集合問題については、以下の記事が参考になります。

qiita.com

ウィキペディアから独立集合の定義を引用します。

グラフ理論における独立集合（どくりつしゅうごう、英: independent set）または安定集合（英: stable set）は、1つのグラフ内で互いに隣接していない頂点の集合である。すなわち、頂点の集合 V で、V の任意の2つの頂点をつなぐ辺が存在しない場合をいう。等価的に、そのグラフの各辺の高々一方の端点のみが V の元である。独立集合の大きさとはその中の頂点の個数である。

独立集合 - Wikipedia

ここでは、'.'をグラフの頂点とみなすことで、「互いに隣接していない頂点集合」というのが、今回の問題の条件を満たしています。

ということで、二部グラフの最大独立集合のサイズを求めるには以下の等式を用います。 蟻本に載っています。

(孤立点のないグラフに対し、)|最大安定集合| + |最小点カバー| = |V|

最小点カバー問題は最大マッチング問題に帰着できるので、

|最大安定集合| + |最大マッチング| = |V|

はの頂点のサイズです。

よって、あとは二部グラフの最大マッチングのサイズが分かればこの問題を解くことができます。

二部グラフの最大マッチング問題は最大フロー問題に帰着できるので、最大フローを求めても良いのですが、ここでは、増加路を使ったアルゴリズムで解きたいと思います。

増加路については以下の記事が参考になります。

二部グラフのマッチング [いかたこのたこつぼ]

この記事の定義を引用させていただきますと、増大路とは、以下のようなパスです。

• 既にマッチングがある （マッチング: ペアとなる2頂点を結ぶ辺の集合）
• ペアのいない（ のどの辺の端点にも含まれない）側の点 を始点とする
• 「 に含まれない辺」と「含まれる辺」を交互に辿る
• ペアのいない（のどの辺の端点にも含まれない）
• 側の点 を終点とする

図で表すと以下のようなグラフで、オレンジと緑の辺を交互に用いるパスが増加路です。 緑色の辺はに含まれている辺で、オレンジ色の辺はに含まれていない辺で増加路に含まれる辺です。

さて、この増加路のオレンジの辺と緑の辺の色を反転させると、の大きさを1増やすことができます。

これを増加路が見つからなくなるまで繰り返すことで、大きさが最大のを見つけることができます。

これで最大マッチングが求まったので、この問題が解けました。

提出

// 入力
int R, C;
char c[41][41];

//  ------------------------------------------
// 最大マッチング
int match[3000], d[41][41];
bool used[3000];
vii g[3000];
int vertex;

void add_edge(int x, int y) {
  g[x].pb(y);
  g[y].pb(x);
}

bool dfs(int v) {
  used[v] = true;
  for (auto u : g[v]) {
    int 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, 0, vertex) {
    if (match[v] < 0) {
      memset(used, false, sizeof(used));
      if (dfs(v)) res++;
    }
  }
  return res;
}
//  ------------------------------------------

signed main() {
 cin.tie(0);
 ios::sync_with_stdio(false);
  cin >> R >> C;
  rep(i, 0, R) rep(j, 0, C) cin >> c[i][j];
  rep(i, 0, R) rep(j, 0, C) {
    if (i+1 <= R && c[i][j] == '.' && c[i+1][j] == '.') {
      add_edge(d[i][j], d[i+1][j]);
    }
    if (j+1 <= C && c[i][j] == '.' && c[i][j+1] == '.') {
      add_edge(d[i][j], d[i][j+1]);
    }
    if (c[i][j] == '.') vertex++;
  }
  cout << vertex - bipartite_matching() << endl;
  return 0;
}

Submission #5326665 - SoundHound Inc. Programming Contest 2018 (春)

感想

グラフ系の問題、やんなんとなぁ。