YuKiCoder No.943 取り調べ

リンク

No.943 取り調べ

Tester解

以下、Tester解です。

$N$人のメンバーを全員自白させるための最小コストを求めます。
制約が$N{\leq}18$のため、ビット全探索($2^{18}=262144$)の方針が立ちます。

まず、問題で問われていることをシンプルに言い換えると以下になります。

$N$人の人がいます。
$i$人目は集合$M_i$の人間を信頼しており、集合$M_i$の人間が全員自白すれば、$i$人目も自動的に自白します。
ただし、$i$人目がそもそも誰も信頼していなければ、自動的に$i$人目は最初から自白します。
最初から自白する人間を自由に決めて良い時、最小コストはいくらでしょうか?

誰かに嘘をつくというよりは、実際に自白したと仮定すると楽になります。

ここで、各$i$人目が信頼している$M_i$の人間関係を有向グラフとして捉えてみます。
つまり、$i$人目の人間から、${\forall}j{\in}M_i$を満たす$j$に向かって、信頼しているという有向辺を引くことができます。
そして、$i$人目の人間が、信頼している人間の数$|M_i|$を余裕度$T_i$ということにします。
余裕度$T_i$が$0$になったとき、自白をしてしまいます。

自白する人間の集合$bit$を、ビット全探索することにします。
これはたかだか$2^{18}=262144$しかかかりません。
ここで、自白する人間$j$の立場に立つと
「自分$j$のせいで、$j$を信頼している他の人間$i$の余裕度が下がる」
ということになります。

よって、トポロジカルソートの際と同様の処理をします。
具体的には
自白すると分かった人間$j$をキューにぶち込みます。
そして、キューが空になるまで、$j$をキューから取り出し、$i{\to}j$を満たすような人間$i$の余裕度が$1$だけ減るため、$F_i$を減らしてあげます。
そして、$F_i=0$のとき、自白するため人間$i$もキューにぶち込むと良いです。

キューが空になるまで処理をした後、全員自白していれば$bit$は条件を満たすため
対応するコストを$A$から計算し、最小値を全探索すればよいです。

//------------------------------------------  
//------------------------------------------  



bool isGood(int N, int bit, vector<vector<int>> &X) {  
    vector<int> in(N, 0);  
    vector<bool> expanded(N, false);  
    for (int i = 0; i < N; i++) {  
        for (int j = 0; j < N; j++) {  
            if (X[i][j]) {  
                in[i]++;  
            }  
        }  
    }  

    queue<int> Q;  
    for (int i = 0; i < N; i++) {  
        if (bit & (1 << i)) in[i] = 0;  
        if (in[i] == 0) Q.push(i);  
    }  

    while (!Q.empty()) {  
        auto d = Q.front();  
        Q.pop();  
        if (expanded[d]) continue;  
        expanded[d] = true;  
        for (int i = 0; i < N; i++) {  
            if (X[i][d] && !expanded[i]) {  
                in[i]--;  
                if (in[i] == 0) {  
                    Q.push(i);  
                }  
            }  
        }  
    }  

    bool good = true;  
    for (int i = 0; i < N; i++) if (!expanded[i]) good = false;  
    return good;  
}  

int main() {  

    int N;  
    cin >> N;  

    vector<vector<int>> X(N, vector<int>(N));  
    cin >> X;  

    vector<int> A(N);  
    cin >> A;  

    int ans = INT_MAX;  
    for (int bit = 0; bit < (1 << N); bit++) {  
        int cost = 0;  
        for (int i = 0; i < N; i++) {  
            if (bit & (1 << i)) {  
                cost += A[i];  
            }  
        }  
        if (isGood(N, bit, X)) ans = min(ans, cost);  
    }  

    cout << ans << endl;  

    return 0;  
}  

感想

難しい、トポロジカルソートの問題にしか見えなかった。
公式解は、ビット演算で高速化していてはえ^になった、もっと勉強しないと駄目だなぁ・・・