kmjp's blog

競技プログラミング参加記です

TopCoder SRM 645 Div1 Medium ArmyTeleportation

SRM

あと一歩で赤だったのに…。
http://community.topcoder.com/stat?c=problem_statement&pm=13346

問題

２次元座標上でN個の点の座標(X1[i],Y1[i])が与えられる。
そこに３つの塔の座標(XT[i],YT[i])が与えられる。

いずれか１個の塔を指定して魔法を唱えると、N個の点はその塔を中心として点対称の位置に移動する。
適切に魔法を唱える順を指定し、N個の点が(X2[i],Y2[i])に来るようにできるか答えよ。

解法

最近解いた問題の知見が活きる。
New Year Contest 2015 : D - ジャンプ - kmjp's blog

この時の知見によると、２回魔法を唱えると元の位置と関係なく平行移動できる。
その移動量は、２回で選択した２つの塔の差分ベクトルの２倍となる。

よって以下の４通りのうちいずれかで条件を満たす移動ができるかチェックすればよい。

  • 魔法を偶数回、すなわち全体の平行移動だけで(X1,Y1)を(X2,Y2)に移動する。
  • (XT[0],YT[0])で１回魔法を唱えた跡、後は全体の平行移動だけで(X1,Y1)を(X2,Y2)に移動する。
  • (XT[1],YT[1])で(以下同文)
  • (XT[2],YT[2])で(以下同文)

初回の１回の魔法を唱え終えたあとの状態を考える。
全体の平行移動だけで(X1,Y1)を(X2,Y2)に移動できるなら、(X1,Y1)と(X2,Y2)それぞれをソートすると、(X2[i]-X1[i],Y2[i]-Y1[i])は各iについて一致しなければならない。

一致する場合、dx=X2[i]-X1[i]、dy=Y2[i]-Y1[i]とする。
２回の魔法の移動ケースは以下の３通り(符号の正負も含めれば6通り)ある。

  • ±(XT[2]-XT[0],YT[2]-YT[0])
  • ±(XT[2]-XT[1],YT[2]-YT[1])
  • ±(XT[1]-XT[0],YT[1]-YT[0])

ただ、この３つの移動ケースは従属であり実際は２つあれば他のケースも表現できる。

１つ目のケースを(WX0,WY0)=(XT[2]-XT[0],YT[2]-YT[0])、(WX1,WY1)=(XT[2]-XT[1],YT[2]-YT[1])とする。
あとはWX0*p+WX1*q=dx、WY0*p+WY1*q=dyを満たす整数解p,qが存在すれば、題意を満たす移動ケースが存在することになる。
ここまで来ると、単に連立方程式の解の判定問題に帰着できる。

まず、係数行列の行列式WX0*WY1-WX1*WY0が非0なら、実際に自明に解を求めることができるので、それが整数か求めればよい。
問題は行列式が0の場合である。そのような場合、以下のケースでは題意を満たさない。

  • WX0=WX=1かつdx!=0なら、方程式を満たすp,qはない
  • WY0=WY=1かつdy!=0なら、方程式を満たすp,qはない
  • dxがWX0,WX1の最大公約数の倍数でないなら、p,qは整数解になりえない
  • dyがWY0,WY1の最大公約数の倍数でないなら、p,qは整数解になりえない
  • 片方の式がもう片方を何倍かしたものなら解が無限にあり、逆にそうでないなら解は０個である。
class ArmyTeleportation {
	public:
	int N;
	pair<ll,ll> P[51];
	pair<ll,ll> Q[51];
	ll wx0,wx1,wy0,wy1;
	
	bool okok() {
		ll dx,dy,i;
		sort(P,P+N);
		sort(Q,Q+N);
		dx=Q[0].first-P[0].first;
		dy=Q[0].second-P[0].second;
		FOR(i,N) if(Q[i].first-P[i].first!=dx) return false;
		FOR(i,N) if(Q[i].second-P[i].second!=dy) return false;
		
		if(dx==0 && dy==0) return true;
		
		ll d=abs(wx0*wy1-wx1*wy0);
		if(d!=0) {
			ll rx=abs(wy1*dx-wx1*dy);
			ll ry=abs(-wy0*dx+wx0*dy);
			return (rx%d==0)&&(ry%d==0);
		}
		
		if(wx0==0 && wx1==0 && dx) return false;
		if(wy0==0 && wy1==0 && dy) return false;
		
		ll gx=__gcd(wx0,wx1), gy=__gcd(wy0,wy1);
		if(wx0==0 && wx1==0) return dy%gy==0;
		if(wy0==0 && wy1==0) return dx%gx==0;
		if(dx%gx || dy%gy) return false;
		
		if(wx0*dy!=wy0*dx) return false;
		return true;
	}
	
	string ifPossible(vector <int> x1, vector <int> y1, vector <int> x2, vector <int> y2, vector <int> xt, vector <int> yt) {
		int i,j;
		
		wx0=2*(xt[2]-xt[0]); wy0=2*(yt[2]-yt[0]);
		wx1=2*(xt[2]-xt[1]); wy1=2*(yt[2]-yt[1]);
		
		N=x1.size();
		FOR(i,N) P[i]=make_pair(x1[i],y1[i]);
		FOR(i,N) Q[i]=make_pair(x2[i],y2[i]);
		if(okok()) return "possible";
		FOR(j,3) {
			FOR(i,N) P[i]=make_pair(2*xt[j]-x1[i],2*yt[j]-y1[i]);
			if(okok()) return "possible";
		}
		return "impossible";
	}
}

まとめ

解がないケースを本番中丁寧に列挙できなかった…。
うーん、せっかくNYCの効果であっさりアプローチを思いついたのに残念。