今回日本人が上位に多かった原因。
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を超える幅が登場しなかったため、すんなり通ってしまった。
実際はその処理にバグだらけで、結局通すまでだいぶデバッグに苦労した。