Codeforces ECR #126 : F. Teleporters

実装は軽い。
https://codeforces.com/contest/1661/problem/F

問題

数直線上に、原点含めてN個の移動可能な点が指定される。
座標がa,bである2点間の移動コストは(a-b)^2とする。

原点から、最も遠い点まで移動したいが、その時総コストをM以下にしたい。
最小で何個移動可能な点を追加すればよいか。

解法

区間毎に、点を1個足したときに総コストが減る量の最大値を二分探索しよう。

int N;
ll A[202020],M;
vector<ll> D;


ll f(ll len, ll sp) {
	ll a=(len+sp)/(sp+1);
	ll b=len/(sp+1);
	return len%(sp+1)*a*a+(sp+1-len%(sp+1))*b*b;
}

pair<ll,ll> gh(ll c) {
	ll g=0,h=0;
	FORR(d,D) {
		ll cur=0;
		int i;
		for(i=29;i>=0;i--) if(cur+(1LL<<i)<d && f(d,cur+(1LL<<i)-1)-f(d,cur+(1LL<<i))>=c) cur+=1<<i;
		g+=cur;
		h+=f(d,cur);
	}
	return {g,h};
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	
	
	cin>>N;
	ll S=0;
	FOR(i,N) {
		cin>>A[i+1];
		D.push_back(A[i+1]-A[i]);
		S+=D.back()*D.back();
	}
	cin>>M;
	
	if(S<=M) {
		cout<<0<<endl;
		return;
	}
	
	ll cur=(1LL<<60)-1;
	for(i=59;i>=0;i--) {
		auto p=gh(cur-(1LL<<i));
		if(p.second>M) cur-=1LL<<i;
	}
	auto ret=gh(cur);
	ll dif=ret.second-M;
	
	
	ret.first += (dif+cur-2)/(cur-1);
	cout<<ret.first<<endl;
	
}

まとめ

二分探索で行けそうなことは割とすぐ考察できるが、実際何を二分探索するかで戸惑う問題。