読者です 読者をやめる 読者になる 読者になる

解いた問題のソースコードと解説など。


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));
  }
};
しょげないでよBaby 眠れば治る