SRM570 Div2 Medium "RobotHerbDiv2"
問題
http://community.topcoder.com/stat?c=problem_statement&pm=12425
訳
ロボットに整数の配列aを与えると各iにおいて以下のように動く。
まず、a[i]だけ前進する。 その後、a[i]だけ90度右に回転する。
最初ロボットは座標(0, 0)で北向き(yの正方向)に立っている。
ロボットに整数の配列aをT回与えたとき、
座標(0,0)からどれだけ離れた場所いるかを返せ。
2点(x1, y1) (x2, y2)の距離はabs( x1 - x2 ) + abs( y1 - y2 )と定義する。
制約
1 <= T <= 100
1 <= aの整数 <= 50
1 <= aの長さ <= 4 * 10^5
考えた事
素直にシミュレートすると計算量は最大で4000万
これでいける。
(後で気付いたけどx,yはintの範囲を超えないね)
ソースコード
class RobotHerbDiv2 { public: int getdist(int T, vector <int> a){ int d = 0; int dx[] = { 0, 1, 0, -1 }; int dy[] = { -1, 0, 1, 0 }; int x = 0, y = 0; for( int i = 0; i < T; i++ ){ for( int j = 0; j < a.size(); j++ ){ x += dx[d] * a[j]; y += dy[d] * a[j]; d += a[j]; d %= 4; } } return abs( x ) + abs( y ); } };