これも割とすんなり。
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; }
まとめ
意外に力技で行く問題。