問題:AtCoder Beginner Contest 190: E - Magical Ornament
解説
解説動画まんまかもしれません。
魔法石が個あります。
各魔法石は隣り合わせになっていいやつが決まっています。重要魔法石の集合をすべて含んでいるように魔法石を1列に並べたとき、必要な魔法石の最小値はいくつですか?もし作れないなら-1を出力しなさい。という問題。
余談ですが、UnionFindすれば「作れない」のみを判定できる。意味ないけど。
入力例1の「隣り合っていい魔法石」をグラフで図示すると、以下のような感じになる。(赤が重要魔法石)
この問題は、「重要魔法石を少なくとも1回通るときの、最小経路問題」と言い換えることができる。
直感的に、スタートは必ず重要魔法石からになりそうだと気づく。重要でない魔法石からスタートした場合、必ず余計な経路を通ったり、往復が必要になるからである。
難しいのが、「少なくとも1回通る」というのをどう考えればよいのかという部分である。
たとえば、以下のグラフを考える。
どう考えても、魔法石3は2回通る必要がありそうだ。これをどう実装すればいいのか皆目検討もつかなくてくまった。
ここで、重要でない魔法石をグラフから消して、重要魔法石のみを抜き出した重み付きグラフに変換してみると、解法が見えてくる。
これでもまだ「少なくとも1回通る」というのをどう考えればいいのかわからないが、頂点数がKまで減った。Kは制約により17以下であり、めちゃくちゃ小さい。
なので、すべての重要魔法石に辺が張られているとみなして、すべての経路を全探索してしまっても間に合う問題になっている。
すべての重要魔法石に辺が張られているとみなしたときの、各魔法石へ辿り着くコストは以下のようになる。
この時点で「すべての重要魔法石を1回通る経路のうち最小のものは?」という問題に言い替わり、これは巡回セールスマン問題である。
巡回セールスマン問題はbitDPで解く。
巡回セールスマン問題のbitDPでの解き方は、以下の問題の解説動画がとても詳しい。
また、巡回セールスマン問題の練習問題として以下がある。
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_2_A&lang=ja
各重要魔法石へ辿り着くコスト計算表は、BFSで計算する。すべての重要魔法石をスタート地点としたときのコスト計算表が必要なので、BFSはK回する。
BFSの一回あたりの計算量はと解説動画で言っていたが、あまりわかっていない。各頂点と各辺を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部分がで、BFS部分が 。全体としてはこれらを足した感じ。
bitDPの~S>>i&1
を~(S>>i&1)
と書いていて5時間くらい溶かしたのは内緒だ。