yukicoder : No.229 線分上を往復する3つの動点の一致

不参加でした。
http://yukicoder.me/problems/617

問題

左右に渡る長さLの線分上を、３つの点P[i]が左右に一定の(それぞれ異なる)速さで往復移動している。
時刻0の状態で３点は線分の左端におり、それぞれ１往復にかかる時間はT[i]である。

時刻0以降で、３点が重なる最初の時間を既約分数の形で答えよ。

解法

結果的に式はEditorialと近いけど、一応自分が考えた解を記載。

線分の長さL=T[0]*T[1]*T[2]とすると、３点の移動の速さS[i]=2*L/T[i]が整数となり処理がしやすい。

時刻TでP[0]とP[1]が同じ向きで重なる場合、T*S[0]≡T*S[1] (mod 2L)なので変形してT(S[0]-S[1])≡0である。
時刻TでP[0]とP[1]が逆の向きで重なる場合、T*S[0]≡2L-T*S[1] (mod 2L)なので変形してT(S[0]+S[1])≡0である。

すなわち、Tは(2L/(S[0]-S[1]))か(2L/(S[0]+S[1]))の倍数なら条件を満たせる。
さらに、P[0]とP[2]について同様に考えると、Tは(2L/(S[0]-S[2]))か(2L/(S[0]+S[2]))の倍数である。

両タイミングが重なるのは、以下の４通りの何れかでありその最小値を求めればよい。

• 
• 
• 
• 

LCMの中身が分数なのでわかりにくいが、整数a,bに対しで求めればよい。

ll T[4],S[3];
ll bo=1LL<<40,si=1;

void solve() {
	int i,j,k,l,r,x,y; string s;
	cin>>T[0]>>T[1]>>T[2];
	T[3]=2*T[0]*T[1]*T[2];
	S[0]=T[1]*T[2]*2;
	S[1]=T[0]*T[2]*2;
	S[2]=T[0]*T[1]*2;
	
	FOR(i,4) {
		ll a=S[0]+((i&1)?S[1]:-S[1]);
		ll b=S[0]+((i&2)?S[2]:-S[2]);
		ll bobo=T[3];
		ll sisi=__gcd(a,b);
		ll g=__gcd(sisi,bobo);
		bobo/=g, sisi/=g;
		if(bo*sisi>bobo*si) bo=bobo, si=sisi;
	}
	_P("%lld/%lld\n",bo,si);
	
}

まとめ

ちょっと頭を使う問題。