昔はダメだったのに、最近読んだらすんなり読解成功したので解いた。今年は合宿まで行ったのに今さらという感じだが。
問題:
なんか2つの事務所があります。
それぞれの事務所には部屋(長方形のマスみたいな感じ)で、複数あります。
それぞれの事務所には始点があって、隣接したマスにある一定の認証レベルがあると移動できる仕組みです。
合計でR個の部屋を見学させたいです。(片方の事務所が0部屋でも良い)。
認証レベルはそれぞれの事務所に独立で与えることができます。要するに2つの事務所にそれぞれ認証レベルを設定したいのですが、できるだけその認証レベルの和が小さくなるようにしたいです。最小どんくらいでいけますか。
解法:
・"可能な限り低い認証レベルでたどり着く場合に"ある認証レベルでたどり着ける部屋の数っていうのはダイクストラみたいなノリで小さい部屋から確定していくことによって求まる。これ求めれると嬉しい。辺の数が高々4本と定数なので、これは|V| = WHと置くと、O(|V| log |V|)で求まる。
・次に認証レベル毎にたどり着ける部屋の数を記録したやつの累積和を求める。
・そん次に片方を決め撃ちして、累積和取ったやつを二分探索
詳しくはソース。
手抜きにより、非常にloglogした計算量になっているので遅い。AOJで0.7sくらい。
結果として、『ダイクストラもどき + レベルを出現したやつだけに圧縮して累積和 + 二分探索』で解きました。
#include <iostream> #include <queue> #include <algorithm> #include <map> #include <cstring> #include <climits> using namespace std; struct NODE{ int x,y,cst; NODE(int x,int y,int cst) : x(x) , y(y) , cst(cst) {} }; bool operator < (const NODE &a,const NODE &b){ return a.cst > b.cst; } int room[500][500]; bool flag[500][500]; int from[500*500]; int main(){ int R; while(cin >> R && R){ map<int,int> result[2]; // (key,value) = (認証レベル,たどり着けた部屋の数) result[0][0] = 0; // 認証Lvが0の時0部屋たどり着ける。 result[1][0] = 0; // 〃 /*今までにたどり着いた認証レベルが小さいものから優先的に部屋を確定していって、その認証レベルで何部屋たどり着けるか記録する段階。*/ for(int i = 0 ; i < 2 ; i++){ int W,H,sx,sy; cin >> W >> H >> sx >> sy; sx--,sy--; for(int y = 0 ; y < H ; y++) for(int x = 0 ; x < W ; x++) cin >> room[y][x]; priority_queue<NODE> Q; Q.push(NODE(sx,sy,room[sy][sx])); memset(flag,0,sizeof(flag)); while(Q.size()){ NODE q = Q.top(); Q.pop(); if(flag[q.y][q.x]) continue; else flag[q.y][q.x] = true; result[i][q.cst]++; int dx[] = {-1,0,1,0} , dy[] = {0,-1,0,1}; for(int d = 0 ; d < 4 ; d++){ int tx = q.x + dx[d] , ty = q.y + dy[d]; if(tx >= 0 && ty >= 0 && tx < W && ty < H && !flag[ty][tx]) Q.push(NODE(tx,ty,max(q.cst,room[ty][tx]))); } } } int ans = INT_MAX; /* 片方の事務所について、ある認証レベルで合計何部屋たどり着けるか累積和取る。 */ vector<int> u; int prev_sum = 0; for(map<int,int>::iterator it = result[1].begin() ; it != result[1].end() ; ++it){ from[u.size()] = it->first; u.push_back(it->second + prev_sum); prev_sum += it->second; } u.push_back(INT_MAX); //番兵 /* もう片方の事務所で、認証レベルいくつにするか(=何部屋使うか)決め撃ちしつつ、累積和取ったやつ二分探索して最小のものを取る。 */ int prev_sum2 = 0; for(map<int,int>::iterator it = result[0].begin() ; it != result[0].end() ; ++it){ int thisLevel = it->first; int thisCount = it->second + prev_sum2; int anotherCount = *lower_bound(u.begin(),u.end(),R-thisCount); if(anotherCount != INT_MAX){ int anotherLevel = from[ lower_bound(u.begin(),u.end(),R-thisCount) - u.begin() ] ; ans = min(ans,thisLevel+anotherLevel); } prev_sum2 += it->second; } cout << ans << endl; } }
