三井住友信託銀行プログラミングコンテスト2019 : F - Interval Running

これも普段の600ptよりは簡単な気がする。
https://atcoder.jp/contests/sumitrust2019/tasks/sumitb2019_f

問題

2人が1次元の数直線で一斉に原点から座標の正方向に走る。
最初のT1分は両者速度A1,B1で走り、次のT2分はA2,B2で走る。
以後T1分・T2分ごとに速度を変える。

両者が同じ位置に来る回数は何回か。

解法

まずコーナーケースを片づけておく。

• (T1+T2)分毎に同じ位置に到達するなら、無限回来る。
• 最初のT1分で先行した方が、あとのT2分で追いつかれない場合、永久に同じ位置に来ないので0回。

残りは、最初のT1分で先行した方が、あとのT2分で追い抜かされる、である。
前者が前半先行する方だとする。
まず最初の(T1+T2)分では1回同じ位置に来るが、以後どうなるかを考える。
(T1+T2)分を1ターンとし、1ターンで後者が距離Xだけ先行したとする。
nターン後は後者がnXだけ先行しており、次のターンで前者が追いつくには、(T1*(A1-B1))≦nXでなければならない。
(T1*(A1-B1))＜nXなら前者が抜いて抜かされて2回同じ位置にきて、後者なら1回追いついた瞬間にまた離される。
よって(T1*(A1-B1)) % X = 0なら(1ターン目に1回だけ同じ位置に来るのも含めて)合計で(2*X/(T1*(A1-B1)))回だけ同じ位置に来るし、(T1*(A1-B1)) % X != 0なら(2*floor(X/(T1*(A1-B1)))+1)回同じ位置に来る。

ll T[2];
ll A[2],B[2];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T[0]>>T[1];
	cin>>A[0]>>A[1];
	cin>>B[0]>>B[1];
	
	ll X=T[0]*A[0]+T[1]*A[1];
	ll Y=T[0]*B[0]+T[1]*B[1];
	
	if(X==Y) {
		cout<<"infinity"<<endl;
		return;
	}
	
	if(A[0]>B[0] && X>Y) return _P("0\n");
	if(A[0]<B[0] && X<Y) return _P("0\n");
	
	ll P=abs(A[0]-B[0]);
	ll D=abs(X-Y);
	ll Z=P*T[0];
	if(Z%D==0) {
		cout<<Z/D*2<<endl;
	}
	else {
		cout<<1+Z/D*2<<endl;
	}
	
}

まとめ

コーナーケースにちゃんと気づけて良かったね。