SRM 273 DIV1 Hard RobotCollision

問題 Editorial

問題

指定されたプログラムcommandsRobbie,commandsSpeedyに従って動くロボット2台がある。
プログラムはU,D,L,Rからなり、それぞれ右・左・上・下に動く。壁の方向に動こうとする場合は動かない。
今xSize*ySizeのグリッドがある。
この任意の位置にそれぞれのロボットを独立に置いた後、同時にプログラムを実行し、ぶつかる確率を求めよ

• 1 <= xSize, ySize <= 100
• 1 <= (|commandsRobbie| = |commandsSpeedy|) <= 10

解答

Editorialを参考にした。
プログラムサイズが小さい。ロボットはたかだかマンハッタン距離がプログラムサイズ以下の場所までしか到達できない。
なので、1つのロボットの位置を全探索・もう1つのロボットの位置は最初に置いたロボットの位置からプログラムのサイズ*2の距離の場所を全探索すればいい。
ぶつかるかどうかは単にシミュレーションすればいい。
これだけでも間に合うが、「どのロボットも壁に当たらないなら平行移動しても同じ」なので真ん中を座標圧縮することもできる

コメント

これができないのは駄目だなー。今だったらEasyで出るよな絶対。
とりあえず、変に小さい制約があったなら、この「サイズによって到達範囲が制限される」感じは気に留めておかないとなー

コード

#include <string>
#include <algorithm>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
using namespace std;
struct RobotCollision {
	double probability(int xSize, int ySize, string commandsRobbie, string commandsSpeedy) {
		static int dx[128], dy[128];
		dx['U'] = dx['D'] = dy['L'] = dy['R'] = 0;
		dy['L'] = dx['U'] = -1;
		dy['R'] = dx['D'] =  1;
		int n = commandsRobbie.size();
		double r = 0;
		rep(x0, xSize) rep(y0, ySize)
		rer(x1, max(0, x0-n*2), min(xSize-1, x0+n*2))
		rer(y1, max(0, y0-n*2), min(ySize-1, y0+n*2)) if(abs(x0-x1) + abs(y0-y1) <= n*2) {
			int i0 = x0, j0 = y0, i1 = x1, j1 = y1;
			if(i0 == i1 && j0 == j1) { r ++; continue; }
			rep(t, n) {
				int ni0 = i0 + dx[commandsRobbie[t]], nj0 = j0 + dy[commandsRobbie[t]];
				if(ni0<0) ni0 = 0; if(ni0>=xSize) ni0=xSize-1;
				if(nj0<0) nj0 = 0; if(nj0>=ySize) nj0=ySize-1;
				int ni1 = i1 + dx[commandsSpeedy[t]], nj1 = j1 + dy[commandsSpeedy[t]];
				if(ni1<0) ni1 = 0; if(ni1>=xSize) ni1=xSize-1;
				if(nj1<0) nj1 = 0; if(nj1>=ySize) nj1=ySize-1;
				if((ni0 == ni1 && nj0 == nj1) || (i0 == ni1 && j0 == nj1 && ni0 == i1 && nj0 == j1)) { r ++; break; }
				i0 = ni0, j0 = nj0, i1 = ni1, j1 = nj1;
			}
		}
		return r / (xSize * ySize * xSize * ySize);
	}
};