Codeforces #190 Div2 C "Ciel and Robot"
問題
http://codeforces.com/contest/322/problem/C
訳
キツネのシエルは2次元座標上を動くロボットを持っていた。始めの位置は(0, 0)である。シエルはロボットに対し、コマンドを書く。コマンドは文字列sで表現される。sの各文字列は1つの操作となる。操作には下記のような4種類ある。
'U' 上に進む(x, y) -> (x, y+1) 'D' 下に進む(x, y) -> (x, y-1) 'L' 左に進む(x, y) -> (x-1, y) 'R' 右に進む(x, y) -> (x+1, y)
文字列sの、左から右へと操作は実行され、それを無限に繰り返していく。位置(a, b)に進む事があるかどうかを出力せよ。
制約
-10^9 <= a, b <= 10^9
1 <= sの長さ <= 100
考えた事
sの文字列長は高々100なので、(a-100, b-100), (a+100, b+100)の四角形の範囲からコマンドをスタートさせて、シミュレートすればよい。
ソースコード
int tx, ty, n; string p; bool chk( int x, int y ){ for( int i = 0; i < n; i++ ){ if( x == tx && y == ty ) return true; if( p[i] == 'U' ) y++; if( p[i] == 'D' ) y--; if( p[i] == 'L' ) x--; if( p[i] == 'R' ) x++; } return false; } int main() { cin >> tx >> ty; cin >> p; n = p.length(); // 一通りコマンドを実行するとどう動くか int u, d, l, r; u = d = l = r = 0; for( int i = 0; i < n; i++ ){ if( p[i] == 'U' ) u++; if( p[i] == 'D' ) d++; if( p[i] == 'L' ) l++; if( p[i] == 'R' ) r++; } int dy = u - d; int dx = r - l; bool ok = false; if( chk( 0, 0 ) ) ok = true; int minX = tx - 100; int maxX = tx + 100; int minY = ty - 100; int maxY = ty + 100; if( dx == 0 && dy != 0 ){ for( int y = minY; y <= maxY; y++ ){ // 符号が違えばだめ if( (y < 0 && dy > 0) || (y > 0 && dy < 0 ) ) continue; // 割り切れないとだめ if( y % dy != 0 ) continue; if( chk( 0, y ) ) ok = true; } } if( dx != 0 && dy == 0 ){ for( int x = minX; x <= maxX; x++ ){ // 符号が違えばだめ if( (x < 0 && dx > 0) || (x > 0 && dx < 0 ) ) continue; // 割り切れないとだめ if( x % dx != 0 ) continue; if( chk( x, 0 ) ) ok = true; } } if( dx != 0 && dy != 0 ){ for( int x = minX; x <= maxX; x++ ){ // 符号が違えばだめ if( (x < 0 && dx > 0) || (x > 0 && dx < 0 ) ) continue; // 割り切れないとだめ if( x % dx != 0 ) continue; int cnt = x / dx; int y = dy * cnt; if( chk( x, y ) ) ok = true; } } cout << (ok ? "Yes" : "No") << endl; }