torus711 のアレ

主に競技プログラミングの問題について書きます.PC 以外だと数式が表示されないかもしれないです

TopCoder SRM 681, Division 2, Level 2 : ExplodingRobots

問題概要

 平面上に二つのロボットを置く.一つは座標 $( x_1, y_1 )$ に,他方は $( x_1, y_1 )$ に置く.
 各ロボットは,$U, D, L, R$ からなる命令列 $\mathit{ instructions }$ を処理する.各命令は,いずれかの座標軸lに垂直な四方向へ距離 $1$ 移動することを表す(正確には問題文参照のこと).しかし,ロボットのプログラムにはバグがあり,命令列の任意の部分列を無視してしまう.これはそれぞれのロボットで独立に発生するので,二つのロボットの動きは異なりえる.
 二つのロボットが同じ座標に存在しようとすると,ロボットは爆発してしまう.
 命令列がどのように無視されても爆発しないならば "Safe" を,そうでないならば "Explosion" を返せ.

  • $-25 \leq x_1, y_1, x_2, y_2 \leq 25$
  • $( x_1, y_1 ) \neq ( x_2, y_2 )$
  • $| \mathit{ instructions } | \leq 50$

解法

 各ロボットは $\mathit{ instructions }$ の任意の部分列を選んで実行することができると考えます.すると,各ロボットについて移動可能な範囲が定まります.このとき,二つのロボットの位置が同じになりえることは,二つのロボットの移動可能範囲に共通部分が存在することに対応します.
 判定の方法を考えます.まず,X 軸方向の移動と Y 軸方向の移動は互いに影響を及ぼさないので,独立に考えることができます.X 軸方向の移動について考えると, $x_1 < x_2$ の場合,ロボット 1 が X 軸正方向へ最大限移動し,ロボット 2 が X 軸負方向へ最大限移動した場合に $x_2 \leq x1$ となるならば,適当な調整で X 座標を同じにできます.$x_2 < x_1$ の場合は逆で,ロボット 1 が X 軸負方向へ最大限移動し,ロボット 2 が X 軸正方向へ最大限移動したときに $x_1 \leq x_2$ となるかを見ます($x_1 = x_2$ のときは自明).Y 軸方向の移動についても同様のことが言えます.X 座標・Y 座標を共に同一にできるならば,且つそのときに限り,答えは "Explosion" です.
 従って,$\mathit{ instructions }$ を走査して各文字の数(=それぞれの方向にどれだけ移動できるか)を数えてから,上記の判定をすることで問題を解くことができます.
 この解法は,$\mathit{ instructions }$ の走査に $O( | \mathit{ instructions } | )$ 時間かかり,判定部分は $O( 1 )$ 時間なので,全体では $O( | \mathit{ instructions } | )$ 時間です(下のコードでは std::map で横着しているので更に $\log$ がかかりますが,文字とインデックスの対応を決めておいて配列で数えれば落とせます).
 実装についてですが,座標を反転させてしまっても大丈夫なので,$x_2 < x_1$ のとき $x_1$ と $x_2$ をスワップして $\mathit{ instructions }$ 中の $L$ と $D$ を入れ替えると,X 軸方向の移動に関して似たような条件式を複数回書かずに済みます(Y 軸方向についても同様).

コード

#define ALL( c ) begin( c ), end( c )

class ExplodingRobots
{
public:
	string canExplode( int x1, int y1, int x2, int y2, string instructions )
	{
		map< char, int > counts;
		for_each( ALL( instructions ), [&]( const char c ){ ++counts[c]; } );

		if ( x2 < x1 )
		{
			swap( x1, x2 );
			swap( counts[ 'L' ], counts[ 'R' ] );
		}
		if ( y2 < y1 )
		{
			swap( y1, y2 );
			swap( counts[ 'U' ], counts[ 'D' ] );
		}
		return x2 - counts[ 'L' ] <= x1 + counts[ 'R' ] && y2 - counts[ 'D' ] <= y1 + counts[ 'U' ] ?  "Explosion" : "Safe";
	}
};