yukicoder : No.62 リベリオン(Extra)

一気に難易度上がった。
http://yukicoder.me/problems/132

問題

基本的にはNo. 61と同じ問題設定である。
yukicoder : No.61 リベリオン - kmjp's blog

ただし、座標や速度の絶対値の上限が10^9になった。

解法

以下の前処理は先に済ませておく。

VX==0またはVY==0の時は容易なので先に処理していく。
VXが負の場合は全体を左右反転、VYが負の場合は全体を上下反転させ、VX,VYは正にしておく。
VXとVYが互いに素でない場合、公約数で割っておき、その分Dを公約数倍する。

ここまでの時点で、VX＞0、VY＞0、VXとVYは互いに素となる。
時間t後に弾が相手に当たるには、0≦t≦Dの範囲で以下のいずれかを満たさなければならない。

HX + t*VX ≡ MX (mod 2*W)、HY + t*VY ≡ MY (mod 2*H)
HX + t*VX ≡ MX (mod 2*W)、HY + t*VY ≡ 2*H-MY (mod 2*H)
HX + t*VX ≡ 2*W-MX (mod 2*W)、HY + t*VY ≡ MY (mod 2*H)
HX + t*VX ≡ 2*W-MX (mod 2*W)、HY + t*VY ≡ 2*H-MY (mod 2*H)

右辺を一般化し、以下を満たすtの存在をチェックすることを考える。

HX + t*VX ≡ TX (mod 2*W)、HY + t*VY ≡ TY (mod 2*H)

整数変数n,mを用いてHX + t*VX = TX + 2*W*n、HY + t*VY = TY + 2*H*mより、(TX + 2*W*n - HX)*VY = (TY + 2*H*m - HY)*VXなので2*W*VY*n + (-2*H*VX)*m = (TY-HY)*VX - (TX-HX)*VYである。

A*n + B*m = Cと置く。
まずCがgcd(A,B)の倍数でない場合は解がない。そうでない場合、全体をgcd(A,B)で割っておく。
拡張ユークリッドの互除法より、A*x + B*y = 1となるx,yが求められる。
よって(A*x + B*y)*C = C = A*n + B*mより、A*(n-C*x)= B*(m-C*y)となる。

そのため整数pを用いてm=(C*y)%A + p*Aと置く。
するとHY + t*VY = TY + 2*H*mよりt=(TY - HY + 2*H*m)/HYとなる。
あとはpを適当に調整して、tが最小の正の数になるようにし、Dと大小判定をすればよい。

上記処理では10^9相当の数を数回乗算を行うので、64bit値では収まらない。
以下ではPythonで通した。

import sys
import fractions

W=H=D=MX=MY=HX=HY=VX=VY=0

def ext_gcd(p,q):
	if q==0:
		return (p,1,0)
	(g,y,x) = ext_gcd(q, p%q)
	return (g,x,y - (p//q)*x)

def calc(tx,ty):
	A = 2*W*VY
	B = -2*H*VX
	C = ty*VX-tx*VY+HX*VY-HY*VX
	
	g = fractions.gcd(A, -B)
	if C % g > 0:
		return False
	A /= g
	B /= g
	C /= g
	
	g,y,x=ext_gcd(B,A);
	
	m = C*y%A
	tv=(ty+2*H*m-HY)/VY;
	
	tv %= 2*H*A/VY;
	if tv<0:
		tv += 2*H*A/VY;
	return tv<=D

Q = input()
while Q > 0:
	Q -= 1
	W,H,D,MX,MY,HX,HY,VX,VY=map(int,raw_input().strip().split())
	
	if VX < 0:
		MX = W - MX
		HX = W - HX
		VX = -VX
	if VY < 0:
		MY = H - MY
		HY = H - HY
		VY = -VY
	
	if VX == 0:
		if MX==HX and ((MY>HY and (MY-HY)<=D*VY) or (MY<HY and (2*H-MY-HY)<=D*VY)):
			print "Hit"
		else:
			print "Miss"
		continue
	
	if VY == 0:
		if MY==HY and ((MX>HX and (MX-HX)<=D*VX) or (MX<HX and (2*W-MX-HX)<=D*VX)):
			print "Hit"
		else:
			print "Miss"
		continue
	
	g = fractions.gcd(VX, VY)
	D *= g
	VX /= g
	VY /= g
	
	if calc(MX,MY) or calc(2*W-MX,MY) or calc(MX,2*H-MY) or calc(2*W-MX,2*H-MY):
		print "Hit"
	else:
		print "Miss"

まとめ

64bit数で収まらないのは難点だが、それ以外はシンプルで面白い問題でした。