torus711 のアレ

主に競技プログラミングの問題について書きます

TopCoder SRM 570, Division 2, Level 2 : RobotHerbDiv2

概要

無限の広さをもつグリッド状の平面にロボットが置かれている。
このロボットは、いずれかの座標軸に直行する向きに 1 マスを単位として動くことができる。

このロボットは数字のシーケンス a を受け取り、a の各要素について次のように動作する

  1. 正面に a[i] だけ進む
  2. a[i] 回、右に 90°回転する

この処理を T 回行ったあとの、初期位置と最終位置のマンハッタン距離を求めよ。

解法

制約が小さく、シミュレーションをしても間に合うので、T 回のループで a を全て処理できます。

コード

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )

const int dir[][2] = {
	0, 1,
	1, 0,
	0, -1,
	-1, 0
};

class RobotHerbDiv2
{
public:
	int getdist( int T, vector <int> a )
	{
		long long y = 0, x = 0, d = 0;

		REP( t, 0, T )
		{
			REP( i, 0, a.size() )
			{
				y += dir[d][0] * a[i];
				x += dir[d][1] * a[i];
				d += a[i];
				d %= 4;
			}
		}

		return abs( x ) + abs( y );
	}
};