yukicoder : No.2221 Set X

これも割とすんなり。
https://yukicoder.me/problems/no/2221

問題

N要素の単調増加な正整数列Aがある。
正整数Xに対し、f(X)は、(X+1)に対し、Aの各要素をfloor(A/X)で置き換えた数列におけるユニークな要素数を掛けた値とする。
f(X)の最小値と、その時のXを求めよ。

解法

f(1)=2Nなので、Xは高々2N-1まで考えればよい。
Xを総当たりしよう。
floor(A[i]/X)とfloor(A[j]/X)が同じ値を取るjの最大値は、Aを二分探索すれば容易に求められる。
これを用いてfloor(A[i]/X)が一致するiの範囲を高速に求めよう。

int N,A[101010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>A[i];
	pair<int,int> ret={2*N,1};
	for(x=2;x<=2*N;x++) {
		int cur=0;
		int step=0;
		while(cur<N&&1LL*(x+1)*step<ret.first) {
			cur=lower_bound(A,A+N,(A[cur]/x+1)*x)-A;
			step++;
		}
		ret=min(ret,{(x+1)*step,x});
	}
	cout<<ret.second<<endl;
	cout<<ret.first<<endl;
}

まとめ

意外に力技で行く問題。