AtCoder ARC #123 : E - Training

本番方針は立ったのだけど、細かいところが詰められず時間切れ。
https://atcoder.jp/contests/arc123/tasks/arc123_e

問題

2人の人X,Yがいる。
それぞれ、初期レベルと、何回練習するごとにレベルが1上がるかという情報が与えられる。

1～N回練習した場合のうち、両者のレベルが一致するのは何パターンあるか。

解法

両者それぞれ、レベル1上がるのに必要な練習回数が一致するケースはコーナーケースとして処理する。

k回練習するとレベルが1上がる、と離散的な値を考えるのは手間なので、それぞれx回練習するとx/kだけレベルが上がる、と連続量で考える。
問題の条件を満たす場合、連続量においてレベル差は1以下である。
そこで以下のケースを考える。

• Xのレベルが、Yのレベルより(連続量で)0以上1未満だけ大きい
• Yのレベルが、Xのレベルより(連続量で)0以上1未満だけ大きい

上記それぞれ、該当する練習回数は区間となる。そこで、X,Yそれぞれfloor_sumを取ってその値を比べれば、両者のレベルが一致しない練習回数がわかる。

int T;
ll N;
ll AX,AY,BX,BY;

ll floor_sum(ll N,ll M,ll A,ll B) {
	// sum(i=0...N-1) floor((A*i+B)/M)
	
	ll ret=0;
	if(B>=M) ret+=N*(B/M), B%=M;
	if(A>=M) ret+=N*(N-1)/2*(A/M), A%=M;
	
	ll Y=(A*N+B)/M;
	if(Y==0) return ret;
	//floor(Y/M)に達するX
	ll X=Y*M-B;
	//Xの右側はY個ずつ
	ret+=(N-(X+A-1)/A)*Y;
	// 90度回転、Y=Nのラインは無視する
	ret+=floor_sum(Y,A,M,(A-X%A)%A);
	return ret;
}



void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>AX>>BX>>AY>>BY;
		
		
		if(BX==BY) {
			if(AX==AY) {
				cout<<N<<endl;
			}
			else {
				cout<<0<<endl;
			}
		}
		else {
			if(AX>AY) swap(AX,AY),swap(BX,BY);
			if(AX==AY&&BX>BY) swap(BX,BY);
			AY-=AX;
			
			if(BX>BY) {
				cout<<0<<endl;
				continue;
			}
			
			ll large=((AY-1)*BY*BX+(BY-BX-1))/(BY-BX);
			ll same=(AY*BY*BX)/(BY-BX);
			ll small=((AY+1)*BY*BX)/(BY-BX);
			
			large=max(large,1LL);
			same=min(same,N);
			small=min(max(same+1,small),N);
			
			ll ret=0;
			
			if(large<=same) {
				ll a=floor_sum(same+1-large,BX,1,large);
				ll b=floor_sum(same+1-large,BY,1,large+AY*BY);
				ret+=same+1-large-abs(a-b);
			}
			if(same<small) {
				ll a=floor_sum(small-same,BX,1,same+1);
				ll b=floor_sum(small-same,BY,1,same+1+AY*BY);
				ret+=small-same-abs(a-b);
			}
			//ret=max(ret,0LL);
			cout<<ret<<endl;
		}
		
		
	}
}

まとめ

floor_sumを使って何とかする部分までは行けたけど、そのあと時間内に詰められないところが弱み。