Mail.Ru Cup 2018 Round 2 : C. Lucky Days

久々にレートが回復してよかった。
http://codeforces.com/contest/1055/problem/C

問題

等間隔で並ぶ２つの区間群[n*Ta+La,n*Ta+Ra]と[n*Tb+Lb,n*Tb+Rb]について最大の共通部分を求めよ。

解法

G=GCD(T0,T1)とする。
するとこの問題は[La,Ra]と[Lb,Rb]をそれぞれG単位でずらせるとき共通部分を最大化せよという問題になる。
そこで、La,Lbをできるだけ0に近づけたケースと、あとどちらかGだけ前後に動かしたケースを考えればよい。

ll L[2],R[2],T[2];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	FOR(i,2) cin>>L[i]>>R[i]>>T[i];
	R[0]++;
	R[1]++;
	ll G=__gcd(T[0],T[1]);
	int a=L[0]/G;
	L[0]-=a*G;
	R[0]-=a*G;
	a=L[1]/G;
	L[1]-=a*G;
	R[1]-=a*G;
	
	ll ma=0;
	for(x=-100;x<=100;x++) 	for(y=-100;y<=100;y++) {
		ll La=L[0]+G*x;
		ll Ra=R[0]+G*x;
		ll Lb=L[1]+G*y;
		ll Rb=R[1]+G*y;
		ll X=max(La,Lb);
		ll Y=min(Ra,Rb);
		ma=max(ma,Y-X);
	}
	cout<<ma<<endl;
}

まとめ

戸惑ったけど無事解けて良かった。