TopCoder SRM 570, Division 1, Level 1 : RobotHerb

問題文

http://community.topcoder.com/stat?c=problem_statement&pm=12427

概要

Division 2, Level 2, RobotHerbDiv2 と制約以外同一。

解法

Div2 のようにシミュレーションをすると TLE してしまいます。

一回の実行での方向の変化により規則性をもつので、以下のように場合分けすることができます。
（一回の移動に於ける座標ごとの距離変化を x, y 、そのマンハッタン距離を m と表記します）

• 方向が変わらない場合：T * m
• 方向が反転する場合（二点を往復する）：T の奇偶によって、奇数なら m 、偶数なら 0
• それ以外（四点を巡回する）：T の mod 4 の値により場合分け
  • 0（一周する）：0
  • 2（対角側の点）：abs( y - x ) + abs( x + y )
  • それ以外：m

コード

typedef long long LL;

#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 RobotHerb
{
public:
	long long getdist( int T, vector <int> a )
	{
		int d = 0;
		LL x = 0, y = 0;

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

		if ( d == 0 )
		{
			return ( abs( x ) + abs( y ) ) * T;
		}
		else if ( d == 2 )
		{
			return T % 2 ? abs( x ) + abs( y ) : 0;
		}
		else
		{
			const int mod = T % 4;

			if ( mod == 0 )
			{
				return 0;
			}
			else if ( mod == 2 )
			{
				return abs( y - x ) + abs( x + y );
			}
			else
			{
				return abs( x ) + abs( y );
			}
		}
	}
};