mayoko’s diary

プロコンとかいろいろ。

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;
    }
};