調べても解説がなかったので
問題概要
原文 → D - 大爆発
日本語なので元の問題文参照
解説
まず自明なケースとして、以下があります。地味に厄介なので最初に弾きましょう。
- ブロックがひとつも存在しない (答えは
)
- 全てのマスにブロックが存在する (答えは
)
これ以外のケースは、少なくとも 1 つはブロックがないマスであり、そこに爆弾を置くと、置いた列に関して全て爆弾がおける状態になるので、必ず目標を達成可能であることがわかります。それでは次に、最小値がどうなるかを考えましょう。
ここでは 行
列目のマスを
と書くことにします。
に爆弾を置くと、以下が成り立ちます。
行目にはブロックがひとつも存在しない
列目にはブロックがひとつも存在しない
ある場所にいったん爆弾を置いてしまえば行・列方向ともに一掃され、その後は各行に爆弾を置けるため、各行において爆弾は 高々 1 回 置いてしまえばよさそうです。行・列の制約は小さめなので、爆弾を置く行を決め打ち して考えることにしましょう。これは 通りありますが制約が小さいのでひとまず大丈夫です。
行を決め打ちすると、爆弾を置かなければならない列がわかります。具体的には以下の条件を満たす列 については少なくとも 1 つ置かなければなりません。(理由は明らかだと思います)
にブロックが存在する場合
これで、「決め打ちした行の集合」と「選ぶべき列の集合」がそれぞれ得られます。図示すると次のようになります。
「決め打ちした行」かつ「選ぶべき列」であって、ブロックが存在しない (= 爆弾をおける) マスを列挙してみましょう。先程までの議論から、爆弾を置くべき行・列それぞれについて、1 個でも置ければ十分ですので、それぞれのマスを頂点と見立てて (行, 列) の二部グラフを作ると、最小辺被覆問題 に帰着されることがわかります。(くわしくは けんちょんさんの記事 を読んでみてください。) 今回のケースにおいては、二部グラフの最大マッチングを求めることで容易に解を求められる問題なので、これで解けそうです。
ただし一点だけ注意しなければならないケースがあります。それは、「決め打ちした行」かつ「選ぶべき列」であるマスに空きマスが 1 つも存在しない場合です。この場合は選択できるマス (= 二部グラフにおける頂点) が存在しないため、そのままでは対応できません。いま、空きマスが全体で少なくとも 1 つ以上存在する場合のみを考えているので、どこかに空きマスがある (= 爆弾をおける) としてよく、そのようなマスに爆弾を置くと元々置きたかった行または列にも置けるようになります。しかし、最初に設置した爆弾は「元々置きたかった行」かつ「元々置きたかった列」に置いているわけではないため、置くべき爆弾の数は合計で 個必要になります。 以上のことに注意すると正答を得られます。
ソースコード
AC コード (tsutaj): Submission #13934922 - 天下一プログラマーコンテスト2012 予選B
// 二部マッチングは略 int main() { int H, W; scanf("%d%d", &H, &W); int block = 0; vector<string> board(H); for(int i=0; i<H; i++) { cin >> board[i]; block += count(board[i].begin(), board[i].end(), '#'); } // 自明なケース if(block == 0) { cout << 0 << endl; return 0; } if(block == H*W) { cout << -1 << endl; return 0; } int ans = INF; // 行の選び方を全部試す for(int bit=0; bit<(1<<H); bit++) { vector<int> xs, ys; // 選んだ行 for(int i=0; i<H; i++) if(bit >> i & 1) xs.emplace_back(i); // 選んでいない行において、ブロックが存在するような列 for(int j=0; j<W; j++) { for(int i=0; i<H; i++) { if(bit >> i & 1 or board[i][j] == '.') continue; ys.emplace_back(j); break; } } Flow<int> fl(H + W + 2); int source = H + W, sink = source + 1; int N = xs.size(), M = ys.size(); for(int i=0; i<H; i++) fl.add_edge(source, i, 1); for(int i=0; i<W; i++) fl.add_edge(H+i, sink, 1); for(auto x : xs) { for(auto y : ys) { if(board[x][y] == '.') fl.add_edge(x, H+y, 1); } } // 行と列の二部マッチング int bm = fl.max_flow(source, sink); // bm が 0 であるとき (どの board[x][y] にもブロックがあるとき) // -> xs, ys の union? であってブロックがないマスが存在するか探す if(bm == 0) { bm = -1; for(auto x : xs) for(int y=0; y<W; y++) if(board[x][y] == '.') bm = 0; for(auto y : ys) for(int x=0; x<H; x++) if(board[x][y] == '.') bm = 0; } if(bm == -1) chmin(ans, min(N, M) - bm); else chmin(ans, N + M - bm); } cout << ans << endl; return 0; }
iwiwi さんのコードをかなり参考にしました (ありがとうございます)
