Codeforces #190 Div1. A. Ciel and Robot

CF#190はA,Bを解き、Cはpretestが通らずじまい。
hackも成功したのでそこそこの順位でした。
http://codeforces.com/contest/321/problem/A

問題

最大100文字のコマンドが与えられる。
各コマンドは、文字U,D,L,Rで構成され、それぞれ2次元座標上を上・下・左・右に1動くことを示す。

原点を出発したロボットが無限回上記コマンドを繰り返したとき、座標(X,Y)を通過するか答えよ。

解法

まず、コマンドを1周する間に(X,Y)を通過するか調べる。
コマンドは100文字までなのでこれは容易。

1周した結果が(X,Y)を通らないまま原点に戻るのであれば、以後何周しても同じところしか通らないので、永遠に(X,Y)は通らない。

それ以外の場合、たとえば1周で(P,Q)するなら、おおよそX/P周かY/Q周の付近で(X,Y)を通る可能性がある。
そこで、X/PまたはY/Q周した地点から、前後10000コマンドぐらいを実際に試してみればよい。
以下のコードでは、X/P-102およびY/Q-102から204周コマンドを試すという処理にしている。

void solve() {
	int f,r,i,j,k,l;
	ll x,y,rx,ry;
	int N;
	ll A,B;
	string S;
	
	cin>>A>>B>>S;
	
	rx=ry=0;
	FOR(i,S.size()) {
		if(S[i]=='U') ry++;
		if(S[i]=='D') ry--;
		if(S[i]=='L') rx--;
		if(S[i]=='R') rx++;
		if(A==rx && B==ry) {
			_P("Yes\n");
			return;
		}
	}
	if(A==0 && B==0) {
		_P("Yes\n");
		return;
	}
	if(rx==0 && ry==0) {
		_P("No\n");
		return;
	}
	
	ll miX,maX,miY,maY;
	if(rx && ry) {
		miX=max(0LL,A/rx-102);
		maX=max(0LL,A/rx+102);
		miY=max(0LL,B/ry-102);
		maY=max(0LL,B/ry+102);
	}
	else if(rx==0) {
		miX=miY=max(0LL,B/ry-102);
		maX=maY=max(0LL,B/ry+102);
	}
	else {
		miY=miX=max(0LL,A/rx-102);
		maY=maX=max(0LL,A/rx+102);
	}
	
	if(miY>maX || miX>maY) {
		_P("No\n");
		return;
	}
	
	x=rx*min(miX,miY);
	y=ry*min(miX,miY);
	FOR(i,max(maX,maY)-min(miX,miY)+2) {
		FOR(j,S.size()) {
			if(S[j]=='U') y++;
			if(S[j]=='D') y--;
			if(S[j]=='L') x--;
			if(S[j]=='R') x++;
			if(A==x && B==y) {
				_P("Yes\n");
				return;
			}
		}
	}
	_P("No\n");
	return;
}

まとめ

他の人はもう少し綺麗に書いてたね。