Codeforces #190 Div2 C "Ciel and Robot"

問題

http://codeforces.com/contest/322/problem/C

訳

キツネのシエルは２次元座標上を動くロボットを持っていた。始めの位置は(0, 0)である。シエルはロボットに対し、コマンドを書く。コマンドは文字列sで表現される。sの各文字列は１つの操作となる。操作には下記のような４種類ある。

'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;
}