yukicoder : No.2718 Best Consonance

こういうのさっと詰めるの難しいな。
https://yukicoder.me/problems/no/2718

問題

N個の整数集合S[i]が与えられる。
S[i]は2値A[i],B[i]で表現され、A[i]の倍数を小さい順にB[i]個入れたものとなる。

異なる2つのS[i]の積集合のうち、最大のサイズを求めよ。

解法

A[i]が同じものが2個以上ある場合、多い順に2つ目のB[i]が解の候補となる。
以後は、A[i]が異なる2つの集合を考える。

A[i]のGCDがGになるもの、すなわちGの倍数であるA[i]について考える。
そのような場合S[i]とS[j]の積集合のサイズはmin(floor(g*B[i]/A[j]),floor(g*B[j]/A[i]))となる。

ここでA[j]*B[j]≦A[i]*B[i]の場合、floor(g*B[j]/A[i])≦floor(g*B[i]/A[j])となる。
よって、A[i]*B[i]が小さい順に処理して行き、A[j]*B[j]≦A[i]*B[i]となるA[j]のうち最小のA[j]に対しfloor(g*B[i]/A[j])が解の候補となる。

int N;
int M[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	int ret=0;
	FOR(i,N) {
		cin>>x>>y;
		ret=max(ret,min(y,M[x]));
		M[x]=max(M[x],y);
	}
	for(i=1;i<=200000;i++) {
		vector<pair<ll,int>> cand={};
		for(j=i;j<=200000;j+=i) if(M[j]) cand.push_back({1LL*j*M[j],j});
		sort(ALL(cand));
		reverse(ALL(cand));
		int ma=1<<30;
		FORR2(a,b,cand) {
			if(ma!=1<<30) ret=max((ll)ret,(ll)i*M[b]/ma);
			ma=min(ma,b);
		}
		
	}
	cout<<ret<<endl;
}

まとめ

この考え方は覚えておこう。