yukicoder : No.61 リベリオン

どこかで見た問題。
http://yukicoder.me/problems/113

問題

W*Hの広さの長方形の領域がある。
座標(Hx,Hy)から、速度(Vx,Vy)で弾を撃つ。
弾は長方形の境界で入射角＝反射角となるように反射する。
D秒以内に座標(Mx,My)に到達するか答えよ。

解法

境界で反射する問題はGoogle Code Jamでも出題されている。
https://code.google.com/codejam/contest/1460488/dashboard#s=p3

まずVxとVyが互いに素になるように、公約数がある場合は両者を公約数で割っておき、その分時間Dを公約数倍しておく。

弾の状態は、(W+1)*(H+1)*4 <= 1024通りしかない。(4通りは、上下方向および左右方向の反射の有無)
よってmin(D,1024)秒分シミュレートすれば、その弾が通りうる全軌道を列挙できる。
あとはその軌道に(Mx,My)が含まれるかチェックすればよい。

以下では、弾のi秒後のX座標をabs(HX+i*VX)%2Wで求めたのち、W以上なら折り返す、というようにしている。Y座標も同様。
こうすると今左右どっちに移動中か管理しなくて良くて楽。

int W,H,D,MX,MY,HX,HY,VX,VY;
int hit[20][20];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	int Q;
	cin>>Q;
	while(Q--) {
		cin>>W>>H>>D>>MX>>MY>>HX>>HY>>VX>>VY;
		ZERO(hit);
		
		int g;
		if(VX==0) g=abs(VY);
		else if(VY==0) g=abs(VX);
		else g=__gcd(abs(VY),abs(VX));
		D*=g;
		VY/=g;
		VX/=g;
		
		FOR(i,min(D+1,257*4)) {
			int dx=abs(HX+i*VX),dy=abs(HY+i*VY);
			dx%=2*W;
			if(dx>W) dx=2*W-dx;
			dy%=2*H;
			if(dy>H) dy=2*H-dy;
			hit[dy][dx]=1;
		}
		if(hit[MY][MX]) _P("Hit\n");
		else _P("Miss\n");
	}
}

まとめ

W,Hがかなり小さいことに気づくと、列挙すればよいことに気づく。