kmjp's blog

競技プログラミング参加記です

Coder-Strike 2014 Round2 - E. Maze 2D

今回日本人が上位に多かった原因。
http://codeforces.com/contest/413/problem/E

問題

高さ2、幅Nのグリッドがあり、各セルの障害物の有無が与えられる。

その後、M個のクエリが与えられる。
各クエリはグリッド上の始点と終点からなる。
各クエリにおいて始点から終点への距離を求めよ。

解法

実はこれ、もっと難しい問題がUTPC2012で出ている。
UTPC2012 : I - 最短路クエリ - kmjp's blog

UTPC2012は点、こちらは辺にコストがあるので若干異なるが、似たアプローチで解ける。
簡単に言えば幅Nを大まかに平方分割して、要所要所の最短コストだけ事前に求めておき、各クエリでは要所から始点ないし終点の距離を求めている。

UTPCでは幅を半分半分と何段階か分割を繰り返したが、今回は√N程度で1回分割すれば間に合う。

今回は幅1000ごとにチェックポイントを設けた。
まず事前処理として、各頂点と左右のチェックポイントまでの最短距離を求めておく。
チェックポイント間のマス数は2000なのでBFSでも余裕で間に合う。
また、チェックポイント間の最短経路も求めておく。

各クエリでは以下のように処理できる。
例えば始点がsx=2500、sy=0、終点がgx=5500、gy=1なら、始点からチェックポイント(3000,0)(3000,1)への最短路を事前計算の結果から求める。
また、前処理の結果から(3000,0)(3000,1)→(4000,0)(4000,1)→(5000,0)(5000,1)というように1000飛ばしで最短距離を求めることができる。
最後に(5000,0)と(5000,1)から(5500,1)までの距離を求めればよい。

int N,M;
string S[2];
const int sp=1000;
ll dist[2][300000][2][2];
ll distsp[300000/sp][2][2];

void dfs(int type,int sx,int sy) {
	int i;

	if(S[sy][sx]=='X') return;
	
	dist[type][sx][sy][sy]=0;
	queue<int> Q;
	Q.push(sx*2+sy);
	while(!Q.empty()) {
		int cx=Q.front()/2;
		int cy=Q.front()%2;
		Q.pop();
		int dx[4]={ 1,-1,0,0}, dy[4]={ 0,0,1,-1};
		FOR(i,4) {
			int tx=cx+dx[i];
			int ty=cy+dy[i];
			if(tx<0 || tx>=N || ty<0 || ty>=2) continue;
			if(type==0 && (tx>=sx+sp || tx<sx)) continue;
			if(type==1 && (tx>sx || tx<=sx-sp)) continue;
			if(S[ty][tx]=='X') continue;
			if(dist[type][tx][sy][ty]<=dist[type][cx][sy][cy]+1) continue;
			dist[type][tx][sy][ty]=dist[type][cx][sy][cy]+1;
			Q.push(tx*2+ty);
		}
	}
}

ll dfs2(int sx,int sy,int gx,int gy) {
	int x,y,i;
	int dis[sp][2];
	if(sx==gx && sy==gy) return 0;
	
	FOR(x,2) FOR(y,sp) dis[y][x]=sp*5;
	dis[0][sy]=0;
	
	queue<int> Q;
	Q.push(sx*2+sy);
	while(!Q.empty()) {
		int cx=Q.front()/2;
		int cy=Q.front()%2;
		Q.pop();
		int dx[3]={ 1,0,0}, dy[3]={ 0,1,-1};
		FOR(i,3) {
			int tx=cx+dx[i];
			int ty=cy+dy[i];
			if(tx>gx || ty<0 || ty>=2) continue;
			if(S[ty][tx]=='X') continue;
			if(dis[tx-sx][ty]<=dis[cx-sx][cy]+1) continue;
			dis[tx-sx][ty]=dis[cx-sx][cy]+1;
			if(tx==gx && ty==gy) return dis[cx-sx][cy]+1;
			Q.push(tx*2+ty);
		}
	}
	return 1LL<<40;
}

void solve() {
	int f,i,j,k,l,x,y;
	
	cin>>N>>M;
	cin>>S[0]>>S[1];
	FOR(i,2) FOR(x,2) FOR(y,2) FOR(k,300000) dist[i][k][x][y]=1LL<<40;
	
	
	for(i=0;i<N;i+=sp) dfs(0,i,0),dfs(0,i,1);
	for(i=0;i<N;i+=sp) dfs(1,i,0),dfs(1,i,1);
	
	FOR(i,N/sp+1) {
		if(i==0 || i*sp>=N) continue;
		distsp[i][0][0]=distsp[i][0][1]=distsp[i][1][0]=distsp[i][1][1]=1LL<<40;
		if(S[0][i*sp]=='.') {
			distsp[i][0][0]=min(dist[0][i*sp-1][0][0]+dist[1][i*sp-1][0][0],dist[0][i*sp-1][0][1]+dist[1][i*sp-1][0][1]);
			distsp[i][1][0]=min(dist[0][i*sp-1][1][0]+dist[1][i*sp-1][0][0],dist[0][i*sp-1][1][1]+dist[1][i*sp-1][0][1]);
		}
		if(S[1][i*sp]=='.') {
			distsp[i][0][1]=min(dist[0][i*sp-1][0][0]+dist[1][i*sp-1][1][0],dist[0][i*sp-1][0][1]+dist[1][i*sp-1][1][1]);
			distsp[i][1][1]=min(dist[0][i*sp-1][1][0]+dist[1][i*sp-1][1][0],dist[0][i*sp-1][1][1]+dist[1][i*sp-1][1][1]);
		}
	}
	FOR(i,M) {
		cin>>x>>y;
		int sx=(x-1)%N;
		int sy=(x-1)/N;
		int gx=(y-1)%N;
		int gy=(y-1)/N;
		if(gx<sx) swap(sx,gx),swap(sy,gy);
		
		ll  ret=0;
		if(sx/sp==gx/sp) {
			ret=dfs2(sx,sy,gx,gy);
		}
		else {
			int tx=(sx+(sp-1))/sp*sp;
			ll hoge[2];
			hoge[0]=dist[1][sx][0][sy];
			hoge[1]=dist[1][sx][1][sy];
			while(tx+sp<=gx) {
				ll nhoge[2];
				nhoge[0]=min(hoge[0]+distsp[tx/sp+1][0][0],hoge[1]+distsp[tx/sp+1][1][0]);
				nhoge[1]=min(hoge[0]+distsp[tx/sp+1][0][1],hoge[1]+distsp[tx/sp+1][1][1]);
				hoge[0]=nhoge[0];
				hoge[1]=nhoge[1];
				tx+=sp;
			}
			ret=min(hoge[0]+dist[0][gx][0][gy],hoge[1]+dist[0][gx][1][gy]);
		}
		
		if(ret>=1LL<<40) _P("-1\n");
		else _P("%lld\n",ret);
	}
}

まとめ

pretestの範囲ではチェックポイント間隔の1000を超える幅が登場しなかったため、すんなり通ってしまった。
実際はその処理にバグだらけで、結局通すまでだいぶデバッグに苦労した。