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

kmjp's blog

競技プログラミング参加記です

TopCoder SRM 570 Div1 Easy RobotHerb

SRM

SRM570に参加。何とかEasyだけそこそこの時間で解ききってちょっとレート上昇。
http://community.topcoder.com/stat?c=problem_statement&pm=12427

問題

整数値Tと整数値配列Aが与えられる。
ロボットは最初(0,0)にいて上を向いている。整数値配列Aの各要素Bについて、ロボットは向いた方向にBマス進んだうえ、B回だけ90度右回転する。
このような処理を配列Aの全要素順番に適用し、かつそれをT回繰り返した場合の原点からのマンハッタン位置を答える。

解法

まず1周分処理してみる。その時の向きに応じてその後の処理を決める。

  • 1周後また上を向いていたら、その位置をT倍すればよい。
  • 1周後下を向いていたら、もう1周したらもとに戻る。よってTが偶数なら原点、そうでないなら1周分の位置に行く。
  • 1周後左または右を向いていたら、4周したらもとに戻る。よって答えは(T%4)周分の位置に等しい。
class RobotHerb {
	public:
	long long getdist(int T, vector <int> a) {
		int i;
		ll rot=0,cr=0;
		ll x=0,y=0,tx,ty;
		
		FOR(i,a.size()) rot += a[i];
		FOR(i,a.size()) {
			if(cr==0) y+=a[i];
			if(cr==1) x+=a[i];
			if(cr==2) y-=a[i];
			if(cr==3) x-=a[i];
			cr+=a[i];
			cr%=4;
		}

		tx=x;ty=y;
		if(cr==0) {
			tx=x*T;
			ty=y*T;
		}
		else if(cr==1 || cr==3) {
			if(T%4==0) tx=ty=0;
			else if(T%2==0) {
				tx=x+y;
				ty=y-x;
			}
		}
		else if(cr==2) {
			if(T%2==0) tx=ty=0;
		}
		return abs(tx)+abs(ty);
	}
};

まとめ

ほかの解法を見てるともっとスマートなものが多い。
まず最初の1周を向き毎に分岐するのではなくdx,dy配列を使ったりとか。
また、1周後上向き以外は、(T%4)周分再度繰りかえすとか。
うーん、そこら辺のテクニックがあればもっと速く書けそうだ。

今回Mediumが550ptだったし、Easy早解き合戦の時は簡単な書き方を考えないとダメだね。

広告を非表示にする