Codeforces Round #190 Div1A Ciel and Robot

問題

ロボットが最初（0,0）にいて、上下左右にそれぞれ1マスずつ動く命令がUDLRで構成させた命令になります。

命令はstringで与えられ、高々100命令です。
最後の命令まで行ったら最初の命令に戻って延々繰り返します。

（0,0）から命令を無限に実行したとき、（a,b）を通るか判定しなさい。

解法
真面目に考えると場合分けが大変面倒になりそうですが、
命令が高々100なので、大ざっぱなところまで近づいてから十分な回数の個別シミュレーションをしても間に合いそうです。
というわけで、命令ループの終わりまでに(a,b)の100四方くらいまで近づいてきたら、そこから1000回くらい座標移動をシミュレートするという超絶アバウトなプログラムを書いたところ、普通に通りました。
なお割り算に絶対値を取っているので、本来進めないはずの逆側からシミュレーションが始まることもありますが、(a,b)と十分な距離を取っているところからスタートし、ロボはそことは逆側に走っていくので問題ありません。

プログラム

#include<iostream>
#include <fstream>
#include <stdio.h>
#include <stdlib.h>
#define _USE_MATH_DEFINES
#include <math.h>
#include<string>
#include<vector>
#include<cmath>
#include<stack>
#include<queue>
#include<sstream>
#include<algorithm>
#include<map>
#include<complex>
using namespace std;


#define li			long long int
#define rep(i,to)	for(int i=0;i<((int)(to));i++)
#define repp(i,start,to)	for(int i=(int)(start);i<((int)(to));i++)
#define pb			push_back
#define sz(v)		((li)(v).size())
#define bgn(v)		((v).begin())
#define eend(v)		((v).end())
#define allof(v)	(v).begin(), (v).end()
#define dodp(v,n)		memset(v,(li)n,sizeof(v))
#define bit(n)		(1ll<<(li)(n))
#define mp(a,b)		make_pair(a,b)
#define rin	rep(i,n)
#define EPS 1e-10
#define ETOL 1e-8
#define MOD 1000000007
#define p2(a,b)		cout<<a<<"\t"<<b<<endl
#define p3(a,b,c)		cout<<a<<"\t"<<b<<"\t"<<c<<endl

li program[100];
li dx[4]={0,0,-1,1};
li dy[4]={1,-1,0,0};
li a,b,n;

bool check(li x, li y, li limStep){
	li idx=0;
	li step=0;
	if(a==x && b==y)return true;
	
	while(step<limStep){
		x+=dx[program[idx]];
		y+=dy[program[idx]];
		
		if(a==x && b==y)return true;
		
		idx=(idx+1)%n;
		step++;
	}
	return false;
}

int main(){
	cin>>a>>b;
	if(a==0 && b==0){
		puts("Yes");
		return 0;
	}
	
	string s;
	cin>>s;
	
	n=sz(s);
	rin{
		if(s[i]=='U')program[i]=0;
		else if(s[i]=='D')program[i]=1;
		else if(s[i]=='L')program[i]=2;
		else program[i]=3;
	}
	
	if(max(abs(a),abs(b)) < 100){
		if(check(0,0,n*1000))puts("Yes");
		else puts("No");
		return 0;
	}
	
	li x1=0, y1=0;
	rin{
		x1+=dx[program[i]];
		y1+=dy[program[i]];
	}
	
	li step;
	
	if(x1==0 && y1==0){
		puts("No");
		return 0;
	}
	else if(x1==0)step=(abs(b)-100)/y1;
	else if(y1==0)step=(abs(a)-100)/x1;
	else step=min((abs(a)-100)/x1,(abs(b)-100)/y1);
	
	step=abs(step);
	if(check(x1*step,y1*step,n*1000))puts("Yes");
	else puts("No");
	
	return 0;
}