kojingharangの日記

SRM 570 Div1 250 RobotHerb

22:19 |

• 長さ N の数列 A に対して、「i=0～N-1 に対して順番に、前進を A[i] 回→右90度回転を A[i] 回する操作」を T 回行う。最初の位置から最後の位置までのマンハッタン距離を求める問題。
• 1≦T≦1,000,000,000, 1≦N≦50, 1≦A[i]≦10,000,000

• どんな A でも、4回繰り返すと最初の方向と同じ向きになるので
• 4回繰り返した時の移動量を T/4 倍すると T/4*4 回繰り返したのと同じになる
• 残りの T%4 回はシミュレート

• 方針が決まっても、簡潔に書くには関数に分けるとしたらどこを切り出すべきか、どんな引数にするのか、後で使うから参照にするのかどうなのかとかでちょっと悩む
• 結果的に go の引数に dir は不要だった。

• Accepted

#define ABS(x) (x>=0 ? x : (-x))

class RobotHerb {
	public:
	
	void go(vector<int>& A, ll& x, ll& y, ll& dir) {
		ll dx[] = {0,1,0,-1};
		ll dy[] = {1,0,-1,0};
		REP(i, A.size()) {
			x+=dx[dir]*A[i];
			y+=dy[dir]*A[i];
			dir = (dir+A[i]%4) % 4;
		}
	}
	long long getdist(int T, vector <int> A) {
		ll x4=0,y4=0,dir=0;
		REP(i, 4) go(A, x4, y4, dir);
		ll x=x4*(T/4),y=y4*(T/4);
		cout<<x4<<" "<<y4<<endl;
		REP(i, T%4) go(A, x, y, dir);
		cout<<x<<" "<<y<<endl;
		//return llabs(x)+llabs(y);
		return ABS(x)+ABS(y);
	}
};

ツイートする