torus711 のアレ

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

TopCoder SRM 608, Division 2, Level 1 : OneDimensionalRobotEasy

問題概要

 無限に広い直線上の原点にロボットが置かれている。このロボットは二種類の命令 'L', 'R' を受理する。'L' は左に単位距離動き、'R' は右に単位距離動く。このロボットは、信号が届かなくなることを防ぐため、左方向には -A より大きい座標をもつ点には移動しない。同様に、右方向には B より大きい座標をもつ点には移動しない。このロボットに複数の命令を送ったときの、ロボットの最終位置を求めよ。

解法

 問題文に書かれたとおりにシミュレーションすることで解くことができます。それぞれの命令に従ってロボットを動かした後、座標を [ -A, B ] の区間内に収まるよう修正することで題意と同じ動作をさせることができます。

コード

#define FOR( v, c ) for ( auto &v : c )

class OneDimensionalRobotEasy
{
public:
	int finalPosition( string commands, int A, int B )
	{
		int cur = 0;
		FOR( c, commands )
		{
			cur += c == 'R' ? 1 : -1;
			cur = max( -A, cur );
			cur = min( B, cur );
		}
		return cur;
	}
};