SRM 495 div1 med:CarrotBoxes
解法
まず問題の本質に気が付きましょう。topcoder の解説(http://apps.topcoder.com/wiki/display/tc/SRM+495)がわかりやすいのでそちらを見たほうが良いです。ここでも, 解説の図は topcoder の解説のものを使わせてもらいます。というか, 解説の図を見て「あっ…」って思った人いるんじゃないでしょうか。
まず, information[i][j] == 'Y' が成り立つ整数の組 (i, j) について i -> j の有向辺を引きます。このようにすると, 解説の一枚目のような有向グラフが出来ますね。
このグラフの 7 を最初に選ぶとどうなるでしょうか。3 の情報がわかりますが, もし 3 が empty だった場合, empty box を特定したのでハッピーです。また, 3 が empty でない場合, その情報がわかるので 安心して 3 も開けることが出来ます。よって, 2 の box の情報も連鎖的にわかることになります。
同様に, 8 -> 4 -> 6 も連鎖的にわかる, といったこともわかります。つまり, この問題の本質は「DAG グラフにおいてできるだけ少ない箱を利用して, すべての箱の情報をわかるようにしよう」ということです。
これは, 連鎖の一番先頭の頂点を選んで, その頂点のみを選んでくれば, すべての箱の情報がわかり, これが明らかに最適です。この場合空の箱を開かない確率は, 1 - (開いた箱の数)/(箱の数) となります。。
ただ, 「すべての箱の情報をわかるようにする」ことは, 必ずしも「すべての箱でその箱が空かそうでないかがわかる」ということと同値ではないことには注意です。なぜかというと, ただひとつの箱を除いてすべての箱の情報がわかれば, 残りの箱が空か空でないかはわかるからです。
なので, もしかすると連鎖の一番先頭の頂点を選ぶ順番を工夫することで, 最後の頂点を開く必要がなくなるかもしれないです。これに対処するには, 最後に開く頂点を場合分けすれば良いです。最後に開く頂点以前に, この頂点以外の情報が分かっていれば, 開かなければならない箱の数は 1 減ります。
今の話はすべてグラフが DAG と考えてやっていましたが, 一般のグラフの場合には強連結成分分解すれば良いです。
今回の場合はわざわざライブラリを使わなくても, warshall floyd を使えば間に合います。
const int MAXN = 55; bool d[MAXN][MAXN], used[MAXN], done[MAXN]; class CarrotBoxes { public: double theProbability(vector <string> information) { int n = information.size(); // warshall memset(d, false, sizeof(d)); for (int i = 0; i < n; i++) { d[i][i] = true; for (int j = 0; j < n; j++) { if (information[i][j] == 'Y') d[i][j] = true; } } for (int k = 0; k < n; k++) for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) { d[i][j] |= d[i][k] & d[k][j]; } // top 要素の決定 memset(used, false, sizeof(used)); vector<int> top; for (int i = 0; i < n; i++) { if (used[i]) continue; used[i] = true; // 強連結成分は取り除く for (int j = 0; j < n; j++) { if (d[i][j] && d[j][i]) used[j] = true; } // top かの判定 int cnt = 0; for (int j = 0; j < n; j++) { if (d[j][i] && !d[i][j]) { cnt++; break; } } if (cnt == 0) top.push_back(i); } int tcnt = top.size(); // 一つ省いても良いか for (int i = 0; i < tcnt; i++) { memset(done, false, sizeof(done)); for (int j = 0; j < tcnt; j++) { if (i == j) continue; for (int k = 0; k < n; k++) { if (d[top[j]][k]) done[k] = true; } } bool ok = true; for (int j = 0; j < n; j++) { if (j != top[i] && !done[j]) { ok = false; break; } } if (ok) return 1-1.*(tcnt-1)/n; } return 1-1.*tcnt/n; } };