Particle

競技プログラミングについての雑記

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;
	}
};