Codeforces ECR #095 : F. Equal Product

こういうシンプルな設定の問題、初手どうすればよいか手がつかない。
https://codeforces.com/contest/1418/problem/F

問題

整数N,M,L,Rが与えられる。

• 1≦X1＜X2≦N
• 1≦Y2＜Y1≦M
• L≦X1*Y1=X2*Y2≦R

各X1について、上記を満たす(X1,X2,Y1,Y2)の組が存在すればそれを答えよ。

解法

X1を総当たりする。X1を定めると、Y1の範囲が定まる。
仮にX1:X2=b:a (a＞b)とすると、Y1:Y2=a:bでなければならない。
よって、範囲内にY1の範囲内にaの倍数となるものがあるかをチェックしよう。

この際、Yの範囲に対し、各整数kに対しkの倍数となるものを列挙しておくことを考える。
X1をずらすとYの範囲も徐々にずれるので、尺取り法の要領でdequeを使い上記kの倍数毎の有効なYをちょっとずつずらすことで、Yの列挙を高速化できる。

ll N,M;
ll L,R;
ll A[202020],B[202020];
vector<int> D[202020];
deque<int> cand[202020];
set<int> CD;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	cin>>L>>R;
	
	for(x=1;x<=200000;x++) {
		A[x]=max(1LL,(L+x-1)/x);
		B[x]=min(M,R/x);
		for(y=x;y<=200000;y+=x) D[y].push_back(x);
	}
	int LY=M+1,RY=M+1;
	for(x=1;x<=N;x++) {
		
		if(A[x]>B[x]) {
			cout<<-1<<endl;
			continue;
		}
		
		
		while(A[x]<LY) {
			LY--;
			FORR(d,D[LY]) {
				if(cand[d].empty()) CD.insert(d);
				cand[d].push_front(LY);
			}
		}
		while(B[x]<RY-1) {
			RY--;
			FORR(d,D[RY]) {
				cand[d].pop_back();
				if(cand[d].empty()) CD.erase(d);
			}
		}
			
		vector<int> ret;
		FORR(a,D[x]) {
			auto it=CD.lower_bound(a+1);
			if(it!=CD.end()) {
				int b=*it;
				y=cand[b][0];
				if(1LL*x/a*b<=N) {
					ret={x,y,1LL*x/a*b,1LL*y/b*a};
					break;
				}
			}
		}
		
		if(ret.empty()) {
			cout<<-1<<endl;
		}
		else {
			cout<<ret[0]<<" "<<ret[1]<<" "<<ret[2]<<" "<<ret[3]<<endl;
		}
		
		
	}
}

まとめ

GよりだいぶAC数が少ない。