SRM 646 Div1 Medium TheGridDivOne
制約を見ると明らかに座標圧縮なので、座標圧縮して dijkstra 等のアルゴリズムで最短経路を求めると解ける。
出題された当時は地力 (実装力) が足りず解けなかったが、今見ると、特に難しいところのない素直な問題に見える。
#define N 150 ll d[N][N]; vector<int> x, y, x2, y2; int n; map<int, int> xd, yd; int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; class TheGridDivOne { public: int find(vector <int> x_, vector <int> y_, ll k) { x=x_; y=y_; n = x.size(); x2.clear(); y2.clear(); x2.pb(0); y2.pb(0); rep(i, n) rep(j, 3){ x2.pb(x[i]+j-1); y2.pb(y[i]+j-1);} sort(all(x2)); UNIQUE(x2); sort(all(y2)); UNIQUE(y2); int h = x2.size(), w = y2.size(); rep(i, h) xd[x2[i]] = i; rep(i, w) yd[y2[i]] = i; rep(i, N) fill(d[i], d[i]+N, INF); rep(i, n) d[xd[x[i]]][yd[y[i]]] = -1; d[xd[0]][yd[0]] = 0; priority_queue<P, vector<P>, greater<P>> q; q.push(P(0, xd[0]*N+yd[0])); ll res = 0; while(!q.empty()){ P p = q.top(); q.pop(); int a = p.snd/N, b = p.snd%N; ll l = p.fst; if(l>d[a][b]) continue; rep(i, 4){ int a2 = a+dx[i], b2 = b+dy[i]; if(a2==h) chmax(res, k-l+x2[a]); if(a2<0||a2>h||b2<0||b2>w||d[a2][b2]<0) continue; ll l2 = l+abs(x2[a]-x2[a2])+abs(y2[b]-y2[b2]); if(dx[i]==1) chmax(res, x2[a]+min(l2, k)-l); if(l2<d[a2][b2]){ d[a2][b2] = l2; if(l2<=k) q.push(P(l2, a2*N+b2)); } } } return res; } };