Codeforces #796 : Div1 D. Cute number

D問題の割にコードは短め。
https://codeforces.com/contest/1687/problem/D

問題

f(x)は、x以上最小の平方数とする。
g(x)は、x以下最大の平方数とする。
整数xがcuteであるとは、x-g(x)＜f(x)-xであることを意味する。

整数列Aが与えられる。Aの各要素にKを足し、全要素cuteとなるようにしたい。
最小のKを求めよ。

解法

cuteなxとcuteでないxはそれぞれ交互に区間として現れるが、区間はだんだん長くなっていく。
そのような区間の境界を総当たりしていけばよい。

int N;
ll A[2020202];
vector<ll> V;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>A[i];
	N=unique(A,A+N)-A;
	
	ll cur=0;
	for(i=1;i<=4020200;i++) {
		V.push_back(cur);
		cur+=i;
		V.push_back(cur);
		cur+=i-1;
	}
	
	for(i=2;i<=4020200;i+=2) {
		ll lo=max(0LL,V[i]-A[0]);
		ll hi=V[i+1]-1-A[0];
		ll add=lo;
		for(j=i;j<=4020200&&lo<=hi;j++) {
			if(V[j]-V[i]>15505000) break;
			x=lower_bound(A,A+N,V[j]-add)-A;
			y=lower_bound(A+x,A+N,V[j+1]-add)-A;
			if(x<y) {
				if(j%2==0) {
					hi=min(hi,V[j+1]-A[y-1]-1);
				}
				else {
					lo=max(lo,V[j+1]-A[x]);
				}
			}
		}
		if(lo<=hi) {
			cout<<lo<<endl;
			return;
		}
	}
	
	
}

まとめ

D問題の割にシンプルと思ったら、この回1500ptなのね。