torus711 のアレ

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

TopCoder SRM 570, Division 1, Level 1 : RobotHerb

概要

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 );
			}
		}
	}
};