Codeforces #278 Div1 D. Conveyor Belts

ヒントありだとかなり簡単な問題。
http://codeforces.com/contest/487/problem/D

問題

N*Mのグリッドがある。
各セルはベルトコンベアになっており、そこに置かれたものはベルトの向いているセルの方向に移動する。
ベルトの向きは上・右・左のいずれかである。

そこで以下のQ個のクエリに答えよ。

• 座標(x,y)のセルに置かれたものは、最終的にグリッド外のどの座標に移動するか。もしくは永遠に止まらず動き続けるか。
• 座標(x,y)のセルのコンベアの向きを変える。

なお、後者のクエリは10000個以下である。

解法

高さ数行分ごとに平方分割すればよい。
まず、分割したグリッド群それぞれについて移動先を前計算する。

コンベアは下を向かないため、上の行から順に行先を確定させていけば良い。
また、無限ループになるのは右向きのコンベアと左向きのコンベアが向き合ってる時だけであり、検出は容易である。

前者のクエリについて、分割後のグリッドごとに移動先を辿るだけで良い。
後者のクエリについては、クエリの対象となる分割後のグリッドについてのみ、行先を計算する。

int N,M,Q;
string S[100020];
int toto[100020][11][2];
const int SP=300;

void rebuild(int v) {
	int x,y;
	for(y=v*SP;y<min((v+1)*SP,N);y++) {
		FOR(x,M) if(S[y][x]=='^') {
			if(y%SP==0) toto[y][x][0]=y-1, toto[y][x][1]=x;
			else toto[y][x][0]=toto[y-1][x][0], toto[y][x][1]=toto[y-1][x][1];
		}
		FOR(x,M) if(S[y][x]=='<') {
			if(x==0) toto[y][x][0]=y, toto[y][x][1]=-1;
			else if(S[y][x-1]=='>') toto[y][x][0]=toto[y][x][1]=-2;
			else toto[y][x][0]=toto[y][x-1][0], toto[y][x][1]=toto[y][x-1][1];
		}
		for(x=M-1;x>=0;x--) if(S[y][x]=='>') {
			if(x==M-1) toto[y][x][0]=y, toto[y][x][1]=M;
			else if(S[y][x+1]=='<') toto[y][x][0]=toto[y][x][1]=-2;
			else toto[y][x][0]=toto[y][x+1][0], toto[y][x][1]=toto[y][x+1][1];
		}
	}
	
}

void solve() {
	int i,j,k,l,r,x,y; string s; char c;
	
	cin>>N>>M>>Q;
	FOR(i,N) cin>>S[i];
	FOR(i,(N+SP-1)/SP) rebuild(i);
	
	while(Q--) {
		cin>>s>>y>>x;
		x--,y--;
		if(s[0]=='A') {
			while(0<=y && y<N && 0<=x && x<M) i=toto[y][x][0],x=toto[y][x][1],y=i;
			_P("%d %d\n",y+1,x+1);
		}
		else {
			cin>>c;
			S[y][x]=c;
			rebuild((y)/SP);
		}
	}
}

まとめ

回答者が少ないのは、問題文が長いからかな。
平方分割と気づけばさほど実装も重くないのだけど。