SRM 406 DIV1 Hard ShortPaths
問題
無向重み付きグラフで以下の条件を満たすものgraphが与えられる：
- それぞれの頂点に対して、たかだか1つの単純閉路に含まれる
- それぞれの頂点v,uに対して、vからuへのsimple pathはたかだか1つ
頂点start,finishと正整数kが与えられる。startからfinishへのpathのうち、k番目に短いものの長さを求めよ。ただしk番目が存在しない場合は-1を返せ。
- 2 ≦ |graph| ≦ 50
- graphは問題文の条件を満たす
- 1 ≦ それぞれの重み ≦ 9
- 1 ≦ k ≦ 10^12
- start ≠ finish
解答
まずstartからfinishへの最短路を求める。この時点でパスが存在しない場合-1を返す。
グラフの制約を考えると、最短路上の区間と閉路がくっついているような形になる。くっついている閉路は頂点に対してたかだか1つなので、くっついている区間がかぶることはない。
最短路の長さをpathlenとし、閉路のそれぞれの長さをcyclesとすると、startからfinishへのpathの長さは以下のように表せる："pathlen + Σ (a_i cycle_i)"。また、このときの[a_i]によってのみpathが異なるので、[a_i]を数えればよいことがわかる。
答えを求めるために2分探索をする。このとき"Σ(a_i cycle_i)≦mid-pathlen"となるような[a_i]の数を数えたい。これは明らかにナップサック問題であるので、DPを使うことにする。しかし、最大の答えを見積もるとそれなりに大きく、単純にはできないことがわかる。ここで重要な観察：最大の答えは|cycles|が大きいほど小さい。
実際には、|cycles|が3以上であれば適切に普通のDPでいける。すなわち|cycles|≦2の時に場合分けをして計算する。
| cycles | が0の場合は"k==1 ? pathlen : -1"で、 | cycles | が1の場合は"pathlen + (k-1) * cycles[0]"となることは明らかである。 |
| cycles | が2の場合にはO(√k)でできる。まず、cycles[0]とcycles[1]の大きい方をx,小さい方をyとする。チェックする答えをmとする。すると組み合わせの数は"��_{k=0}^{m/x} (floor( (m-k*x)/y)+1)"となる。つまりxを何個使うかを全探索して、それに対して残りを最大何個使えるかを計算する。+1は0個の場合のため。(m/x)*(m/y)/2がkを超えるなら明らかに大きすぎるので計算を省ける。するとO(√k)となる。ちなみにこれをΘ(log k)で計算する方法も存在する("SRM 410 DIV1 Hard WifiPlanet"参照)。 | ||
| cycles | が3以上の場合は答えはたかだか3000000程度。2分探索のたびにDPしても間に合う。 |
この上限は以下のようにわかる：サイクルのサイズを均等に分けた時に答えが最大になるが、50/3≦17で重み9としても153。組み合わせは最大C(x+1,|cycles|)程度であってC(x,3)≧10^12となるようなxは18200程度で、それに153をかけても2784600程度だから。なお、C(x,y)で組み合わせの数がわかることはa_iをi-1番目の選択とi番目の選択の間の区間として考えればわかりやすい。
コメント
逆指数O(x^(1/y))の上限・アルゴリズム("逆指数"は造語)。
コード
#include <string> #include <vector> #include <cstring> #include <iostream> #define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i)) #define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i)) #define each(it,o) for(__typeof((o).begin()) it = (o).begin(); it != (o).end(); ++ it) #define pb(x) push_back(x) #define mset(m,v) memset(m,v,sizeof(m)) #define INF 0x3f3f3f3f #define INFL 0x3f3f3f3f3f3f3f3fLL using namespace std; typedef vector<int> vi; typedef long long ll; ll dp[3000010]; struct ShortPaths { ll counting(vi ws, ll x) { ll r = 0; if(x < 0) r = 0; else if(ws.size() == 2) { if((ll)(x/ws[0])*(x/ws[1])/2+1 > 1e12) return INFL; if(ws[0]<ws[1])swap(ws[0],ws[1]); int imax = x / ws[0]; for(int i = 0; i <= imax; i ++) r += (x - (ll)ws[0] * i) / ws[1] + 1; }else { if(sizeof(dp)/sizeof(dp[0]) <= x) return INFL; memset(dp, 0, sizeof(dp[0])*(x+1)); dp[0] = 1; rep(i, ws.size()) { int w = ws[i]; rer(j, 0, x-w) if((dp[j+w] += dp[j]) > 1e12) return INFL; } rer(i, 0, x) r = min(r + dp[i], (ll)1e14); } return r; } long long getPath(vector <string> graph, long long K, int s, int t) { vi tmp; tmp.pb(9*17), tmp.pb(9*17), tmp.pb(9*16); static int wf[51][51]; mset(wf, INF); int n = graph.size(); rep(i, n) rep(j, n) if(graph[i][j] != '0') wf[i][j] = graph[i][j] - '0'; rep(k, n) rep(i, n) rep(j, n) wf[i][j] = min(wf[i][j], wf[i][k] + wf[k][j]); if(wf[s][t] == INF) return -1; ll pathlen = 0; vi path; { int i = s; while(1) { path.pb(i); if(i == t) break; for(int j = n-1; j >= 0; j --) if(graph[i][j] != '0' && (graph[i][j]-'0') + (j == t ? 0 : wf[j][t]) == wf[i][t]) { pathlen += graph[i][j]-'0'; i = j; break; } } } cout << "pathlen: " << pathlen << endl; vi cycles; int m = path.size(); rep(i, m) { int j = i; while(j < path.size() && wf[path[j]][path[i]] != INF) j ++; if(j == i) ; else { cycles.pb(wf[path[i]][path[i]]); i = j-1; } } cout << "cycles: "; each(i, cycles) cout << *i << ", "; cout << endl; if(cycles.empty()) return K == 1 ? pathlen : -1; if(cycles.size() == 1) return pathlen + (cycles[0] * (K-1)); ll l = -1, u = cycles.size() == 2 ? 500000000 : 3000000; while(u-l>1) { ll mid = (l+u) / 2; if(counting(cycles, mid) >= K) u = mid; else l = mid; } return pathlen + u; } };
