ベスパリブ

プログラミングを主とした日記・備忘録です。ベスパ持ってないです。

ABC190 E問題

問題:AtCoder Beginner Contest 190: E - Magical Ornament

解説

解説動画まんまかもしれません。


魔法石が N個あります。

各魔法石は隣り合わせになっていいやつが決まっています。重要魔法石の集合 C_Kをすべて含んでいるように魔法石を1列に並べたとき、必要な魔法石の最小値はいくつですか?もし作れないなら-1を出力しなさい。という問題。


余談ですが、UnionFindすれば「作れない」のみを判定できる。意味ないけど。


入力例1の「隣り合っていい魔法石」をグラフで図示すると、以下のような感じになる。(赤が重要魔法石)

f:id:takeg:20210201162651p:plain
入力例1の「隣り合っていい魔法石」を表現したグラフ


この問題は、「重要魔法石を少なくとも1回通るときの、最小経路問題」と言い換えることができる。

直感的に、スタートは必ず重要魔法石からになりそうだと気づく。重要でない魔法石からスタートした場合、必ず余計な経路を通ったり、往復が必要になるからである。


難しいのが、「少なくとも1回通る」というのをどう考えればよいのかという部分である。

たとえば、以下のグラフを考える。

f:id:takeg:20210201163641p:plain
魔法石3は必ず2回通る必要がありそう

どう考えても、魔法石3は2回通る必要がありそうだ。これをどう実装すればいいのか皆目検討もつかなくてくまった。


ここで、重要でない魔法石をグラフから消して、重要魔法石のみを抜き出した重み付きグラフに変換してみると、解法が見えてくる。

f:id:takeg:20210201162832p:plain
重要魔法石のみ抜き出したグラフ

これでもまだ「少なくとも1回通る」というのをどう考えればいいのかわからないが、頂点数がKまで減った。Kは制約により17以下であり、めちゃくちゃ小さい。

なので、すべての重要魔法石に辺が張られているとみなして、すべての経路を全探索してしまっても間に合う問題になっている。

すべての重要魔法石に辺が張られているとみなしたときの、各魔法石へ辿り着くコストは以下のようになる。

f:id:takeg:20210201163034p:plain
重要魔法石の経路コスト表(例:重要魔法石3から重要魔法石0へはコスト2かかる)

この時点で「すべての重要魔法石を1回通る経路のうち最小のものは?」という問題に言い替わり、これは巡回セールスマン問題である。


巡回セールスマン問題はbitDPで解く。

巡回セールスマン問題のbitDPでの解き方は、以下の問題の解説動画がとても詳しい。

atcoder.jp

また、巡回セールスマン問題の練習問題として以下がある。

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_2_A&lang=ja


各重要魔法石へ辿り着くコスト計算表は、BFSで計算する。すべての重要魔法石をスタート地点としたときのコスト計算表が必要なので、BFSはK回する。

BFSの一回あたりの計算量は O(N+M)と解説動画で言っていたが、あまりわかっていない。各頂点と各辺を1回ずつ走査するのでこの計算量か。

コーナーケース

  • 特になし

実装

Pythonだと間に合わなさそうだったのでC++で実装した。

#include <bits/stdc++.h>
using namespace std;


vector<int> BFS(int n, vector<vector<int>>& paths, int& N) {
    // BFSで宝石nから各宝石までの距離を求める
    vector<int> dist(N, INT_MAX); dist[n] = 0;
    set<int> visited; visited.insert(n);
    deque<int> que; que.push_back(n);
    while(!que.empty()) {
        int now = que.front();
        que.pop_front();

        for (int nx: paths[now]) {
            if (visited.count(nx)) continue;
            visited.insert(nx);
            dist[nx] = min(dist[nx], dist[now]+1);
            que.push_back(nx);
        }
    }
    return dist;
}

void solve(){
    int N, M; cin >> N >> M;
    vector<vector<int>> paths(N);
    for (int i=0; i<M; i++) {
        int A, B; cin >> A >> B; A--; B--;
        paths[A].push_back(B);
        paths[B].push_back(A);
    }

    int K; cin >> K;
    vector<int> Cs(K);
    for (int i=0; i<K; i++) {
        int C; cin >> C; C--;
        Cs[i] = C;
    }

    vector<vector<int>> dists;
    for (int i=0; i<K; i++) {
        dists.emplace_back(BFS(Cs[i], paths, N));  // 始点cからの最短距離を求める
    }

    // for (int i=0; i<K; i++) {
    //     cout << "FROM:" << Cs[i] << endl;
    //     for (int j=0; j<K; j++) {
    //         cout << Cs[j] << ":" << dists[i][Cs[j]] << endl;
    //     }
    // }

    // bitDP[S][i] := 既に訪れた重要宝石集合Sにおいて、現在の重要宝石がiのときの、最短距離
    vector<vector<int>> dp(1<<K, vector<int>(K, INT_MAX));
    for (int i=0; i<K; i++) {
        dp[0][i] = 0;
    }
    for (int i=0; i<K; i++) {
        for (int j=0; j<K; j++) {
            dp[(1<<i)|(1<<j)][j] = dists[i][Cs[j]];
        }
    }
    for (int S=1; S<(1<<K); S++) {
        for (int i=0; i<K; i++) {  // 現在の宝石i
            if (~S>>i&1) continue;  // iはまだ訪れていない
            for (int j=0; j<K; j++) {  // 次に行く宝石j
                if (S>>j&1) continue;  // jは既に訪れている
                int new_cost = dp[S][i]+dists[i][Cs[j]];
                if (new_cost<0) new_cost = INT_MAX;  // オーバーフロー対策
                dp[S|1<<j][j] = min(dp[S|1<<j][j], new_cost);
            }
        }
    }

    // 答え
    int ans = INT_MAX;
    for (int i=0; i<K; i++) {
        ans = min(ans, dp[pow(2,K)-1][i]);
    }
    if (ans == INT_MAX) {
        cout << -1 << endl;
    }
    else {
        cout << ans+1 << endl;
    }
}


int main(int argc, char const *argv[]){
    solve();
    return 0;
}

計算量は、bidDP部分が O(2^{K} K^{2})で、BFS部分が O(K (N+M)) 。全体としてはこれらを足した感じ。

bitDPの~S>>i&1~(S>>i&1)と書いていて5時間くらい溶かしたのは内緒だ。