Codeforces #336 Div1 A. Chain Reaction

2連続いまいちな出来でレート減。TCと正反対だ。
http://codeforces.com/contest/607/problem/A

問題

1次元の数直線上にN個のビーコンがある。
各ビーコンは位置X[i]にあり、電源を入れると左側B[i]以内の範囲にあるビーコンを破壊する。
(先に破壊されたビーコンは、他のビーコンを破壊できない)

ここで、全てのビーコンの右側のどこかで、好きな場所に好きな破壊範囲のビーコンを1つ追加できるとする。
右側から順にビーコンに電源を入れたとき、壊されるビーコンの最小数を求めよ。

解法

先にXでビーコンをソートしておく。
右側に好きなサイズのビーコンを置けるということは、右側から順に任意個数のビーコンを破壊できるということになる。
(ソート後で)壊されない右端のビーコンをiとしたとき、0～iのうちで破壊されるビーコンの数と、その右側(N-1-i)個の和が破壊されるビーコンの数となる。

後者は自明なので、前者を求めよう。
それには、X[i]-B[i]より小さい位置のうち最大位置のビーコンをj番目とすると、(j番目を残す場合にその左側で壊すビーコン数)+(i-j-1)が0～iのうちで破壊されるビーコンの数となる。
jは二分探索や尺取法で求められる。

int N;
int A[101010],B[101010];
pair<int,int> P[101010];
int dest[101010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>P[i].first>>P[i].second;
	sort(P,P+N);
	FOR(i,N) A[i]=P[i].first, B[i]=P[i].second;
	
	int ma=N;
	FOR(i,N) {
		x = lower_bound(A,A+i,A[i]-B[i])-A;
		while(x>=0 && A[x]>=A[i]-B[i]) x--;
		if(x>=0) dest[i]=dest[x];
		dest[i] += i-x-1;
		ma=min(ma,dest[i]+(N-1-i));
		
	}
	cout<<ma<<endl;
	
}

まとめ

ビーコンはIIIもVも苦手です。