Codeforces Global Round 31 : D. Insolvable Disks

かなり良い出来だった回。
https://codeforces.com/contest/2180/problem/D

問題

２次元座標において、X軸上にN個の点が指定される。
各点を中心に、任意の半径の円を配置するとする。
ただし円同士が接点以外で共通部分を持ってはならない。

最大何個の接点を作ることができるか。

解法

先頭から順に、半径を定めたとき、ここまでの接点の数を最大化しつつ、それを満たす右端の円の半径の上限下限を保持しよう。
そして、次の点の半径を、接点を増やせる値にできるか判定していけばよい。

int T,N;
ll X[2020202];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		FOR(i,N) {
			cin>>X[i];
			X[i]*=4;
		}
		
		if(N==1) {
			cout<<0<<endl;
			continue;
		}
		ll L=1,R=X[1]-X[0]-1;
		int ret=0;
		for(i=1;i<N;i++) {
			ll TL=1,TR=(i==N-1)?4LL<<30:X[i+1]-X[i]-1;
			if(L+TL<=X[i]-X[i-1]&&R+TR>=X[i]-X[i-1]) {
				ret++;
				ll NR=min(TR,X[i]-X[i-1]-L);
				ll NL=max(TL,X[i]-X[i-1]-R);
				L=NL;
				R=NR;
			}
			else {
				L=1;
				R=(i==N-1)?4LL<<30:X[i+1]-X[i]-1;
			}
		}
		cout<<ret<<endl;
		
	}
}

まとめ

最初方針に困ったけど、終わってみればそんな時間かかってないんだよな。