Good Bye 2015 : F. New Year and Cleaning

Eよりこっちの方が変なハマりせず簡単だった…。
http://codeforces.com/contest/611/problem/F

問題

H*Wの二次元グリッドがある。
H*W個それぞれのマスからロボットを動かし始めることを考える。
ロボットは上下左右の隣接マス移動からなるN個の命令群を順に実行し、グリッド外にはみ出るまで繰り返す。

H*W個の全マスからロボットを動かし始めるとき、グリッド外にはみ出るまでに実行する命令数の総和を求めよ。

解法

ロボットが初期位置からどの程度移動したかを管理し、今までになく左右・上下の移動距離を更新したかどうかを求めよう。
命令によって今までない移動距離に到達すると、元のH*Wのグリッドのうち、どこか1行または1列を開始位置とした場合にロボットがその命令でグリッド外にはみ出る。
そのため、移動距離の更新有無に加え、まだはみ出てないロボットの初期位置(これは矩形になる)を管理しよう。

N個の命令を1周しただけではすべてのロボットがはみ出ない可能性がある。
ただ、1周したことで初期位置からずれが生じている場合、何周も命令を繰り返すことでいずれ全ロボがはみ出る。
そこで、命令のうち移動距離を更新するものだけについて2周目以降も繰り返そう。
H周またはW周する間には全ロボットがはみ出る。

int N,H,W;
string S;
ll mo=1000000007;
ll ret;
ll relx[505050],rely[505050];
ll difx,dify;


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>H>>W;
	cin>>S;
	
	queue<ll> V;
	FOR(i,N) V.push(i);
	
	int L=0,T=0,R=W-1,B=H-1;
	int ML=0,MR=0,MT=0,MB=0;
	
	ll X=0, Y=0;
	while(V.size() && L<=R && T<=B) {
		ll k=V.front();
		V.pop();
		
		if(k<N) {
			if(S[k%N]=='U') Y--;
			if(S[k%N]=='D') Y++;
			if(S[k%N]=='L') X--;
			if(S[k%N]=='R') X++;
			relx[k]=X, rely[k]=Y;
			if(k==N-1) difx=X,dify=Y;
		}
		else {
			X = difx*(k/N)+relx[k%N];
			Y = dify*(k/N)+rely[k%N];
		}
		int num=0;
		if(X<ML) ML--, L++, num = B-T+1;
		if(X>MR) MR++, R--, num = B-T+1;
		if(Y<MT) MT--, T++, num = R-L+1;
		if(Y>MB) MB++, B--, num = R-L+1;
		if(num) {
			(ret += (k+1)%mo*num)%=mo;
			V.push(k+N);
		}
	}
	
	if(L<=R && T<=B) return _P("-1\n");
	cout<<ret<<endl;
}

まとめ

問題設定を読み解くのに少し手間取った。