SRM 570 Div1 Easy RobotHerb
問題
ロボットが2次元座標上に位置している。ロボットの一連の動作が数列aで与えられており、これによるとロボットのi番目の動作は
a[i]前進し、a[i]回右に90度回転する
である。
この一連の動作をT回行った後の到達点と出発点の間のマンハッタン距離を求めよ。
やりかた
数字が大きいので愚直なシミュレーションはできない。
便宜上初期状態ではロボットは原点におり、Y軸正方向を向いているとする。一連の動作を4回繰り返すとかならずまたY軸正方向を向くので、一連の動作を4回繰り返した時のx,yの増分をT/4倍し、残りのT%4回分を足した分のマンハッタン距離を返せばよい。
以下ソース。
class RobotHerb { public: ll labs(ll a){ return a > 0 ? a : -a; } long long getdist(int T, vector <int> a) { ll px = 0; ll py = 0; ll d = 0; for(int k = 0; k < 4; k++){//4回命令を行った時のx,yの増分 for(int i = 0; i < (int)a.size(); i++){ if(d % 4 == 0) py += a[i]; if(d % 4 == 1) px += a[i]; if(d % 4 == 2) py += -a[i]; if(d % 4 == 3) px += -a[i]; d = (d + a[i]) % 4; } } ll rx = 0; ll ry = 0; ll dd = 0; for(int k = 0; k < T % 4; k++){//T%4回命令を行った時のx,yの増分 for(int i = 0; i < (int)a.size(); i++){ if(dd % 4 == 0) ry += a[i]; if(dd % 4 == 1) rx += a[i]; if(dd % 4 == 2) ry += -a[i]; if(dd % 4 == 3) rx += -a[i]; dd = (dd + a[i]) % 4; } } return (ll)(labs(T / 4 * px + rx) + labs(T / 4 * py + ry)); } };
Get up! 明日のSUPER ST@R!