TopCoder SRM 646 Div1 Medium TheGridDivOne、Div2 Medium TheGridDivTwo

気づいてしまえば簡単。
http://community.topcoder.com/stat?c=problem_statement&pm=13630
http://community.topcoder.com/stat?c=problem_statement&pm=13628

問題

２次元座標上の格子点を考える。
原点から開始し、上下左右に隣接する格子点に移動する、という処理を行うことを考える。
なお、移動不可能なN個の格子点の座標(X[i],Y[i])が与えられる。

移動を最大K回行う中で到達可能な格子点のうち、最大のX座標を答えよ。

解法

Div2はKが1000以下。
よって原点からのマンハッタン距離が1000以下の点に対しBFSを行うだけで良い。

Div1はNは47以下と小さいもののKが10^9と大きいのでBFSは行えない。
Nが小さいことから、ほとんどの格子点は自由に移動できる。
そこで座標圧縮することを考えよう。

N個の頂点に対し、X座標はX[i]-1・X[i]・X[i]+1、Y座標はY[i]-1・Y[i]・Y[i]+1のそれぞれ３つだけを考える。
原点に対しても同様にX座標・Y座標それぞれ-1・0・+1だけを考える。
X・Y軸ともにこれら3*(N+1)個以外の座標は互いに自由に移動できるので、無視することができる。
これらの(3*(N+1))*(3*(N+1))個の座標圧縮した点に対してダイクストラ法を行う。

座標圧縮後の点に処理回数K回以下で到達できる場合、残りの回数はできるだけ(移動不可の格子点をまたがない範囲で)X軸正の方向に移動すると考え、X座標の最大値を求めればよい。

int dist[200][200];
int block[200][200];

class TheGridDivOne {
	public:
	int find(vector <int> X, vector <int> Y, int K) {
		int N=X.size(),i,j,x,y;
		map<int,int> mx,my;
		
		my[-1]=my[0]=my[1]=0;
		mx[-1]=mx[0]=mx[1]=0;
		FOR(i,N) mx[X[i]-1]=mx[X[i]]=mx[X[i]+1]=0;
		FOR(i,N) my[Y[i]-1]=my[Y[i]]=my[Y[i]+1]=0;
		
		vector<int> rx,ry;
		ITR(it,mx) it->second=rx.size(),rx.push_back(it->first);
		ITR(it,my) it->second=ry.size(),ry.push_back(it->first);
		rx.push_back(1<<30);
		ry.push_back(1<<30);
		
		FOR(i,200) FOR(j,200) dist[i][j]=1<<30;
		ZERO(block);
		FOR(i,N) block[mx[X[i]]][my[Y[i]]]=1;
		
		dist[mx[0]][my[0]]=0;
		priority_queue<pair<ll,int> > q;
		q.push(make_pair(0,mx[0]*1000+my[0]));
		
		while(q.size()) {
			ll d=-q.top().first;
			int cx=q.top().second/1000;
			int cy=q.top().second%1000;
			q.pop();
			if(dist[cx][cy]!=d) continue;
			FOR(i,4) {
				int dd[4]={1,0,-1,0};
				int ty=cy+dd[i];
				int tx=cx+dd[i^1];
				if(tx<0 || tx>=rx.size() || ty<0 || ty>=ry.size()) continue;
				if(block[tx][ty]) continue;
				if(d+abs(rx[cx]-rx[tx])+abs(ry[cy]-ry[ty])<dist[tx][ty]) {
					dist[tx][ty] = d+abs(rx[cx]-rx[tx])+abs(ry[cy]-ry[ty]);
					q.push(make_pair(-dist[tx][ty],tx*1000+ty));
				}
			}
		}
		
		int ma=0;
		FOR(i,rx.size()) FOR(j,ry.size()) if(dist[i][j]<=K)
			ma=max(ma,rx[i]+min(K-dist[i][j],rx[i+1]-rx[i]-1));
		return ma;
		
	}
}

まとめ

450-500ptでいいと思うけど、なんでこれ600ptなんだろ。