Codeforces #296 Div1 B. Clique Problem

実装はAよりも楽。
http://codeforces.com/contest/528/problem/B

問題

1次元の数直線上にN個の点がある。
各点は位置がX[i]、重さがW[i]である。

ここで、|X[i]-X[j]|≧W[i]+W[j]であるような頂点間に無向辺を張ったグラフを考える。
このグラフの最大クリークの頂点数を求めよ。

解法

各頂点は区間(X[i]-W[i])～(X[i]+W[i])に対応すると考える。
i番の頂点を右端とする最大クリークは、(X[i]-W[i])より左側にある最大クリーク+1と考えることができる。

あとはそうするとあとは単なる区間スケジューリングであり、(X[i]+W[i])の小さい順にソートして「(X[i]-W[i])より左側にある最大クリーク+1」を順次求めていけば良い。

int N;
int ma;
vector<pair<ll,int> > E;
int num[505000];

void solve() {
	int i,j,k,l,r; ll x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>x>>y;
		E.emplace_back(x-y,i+202000);
		E.emplace_back(x+y,i);
	}
	sort(E.begin(),E.end());
	FORR(e,E) {
		if(e.second>201000) num[e.second-202000]=ma+1;
		else ma=max(ma,num[e.second]);
	}
	cout<<ma<<endl;
}

まとめ

本番は区間スケジューリングする際無駄にSegTreeを使ってしまった。