Typical DP Contest : K - ターゲット

これは本番若干方針は立てたけど、そのままやっていたら苦労していた問題。
後で解説聞いたらだいぶあっさりかけた。
http://tdpc.contest.atcoder.jp/tasks/tdpc_target

問題

X軸上に中心が来る円がいくつかある。
この円のうちいくつか選び、小さい円が順に大きな円の内部に来るようにしたい。
最大いくつの円を選べるか。

解法

中心がX[i]、半径がR[i]の円のX軸上の交点のX座標は(X[i]-R[i]),(X[i]+R[i])となる。
(X[i]-R[i]) < (X[j]-R[j]) < (X[j]+R[j]) < (X[j]-R[j])
ならj番目の円はi番目の内部に来る。

ここで思い立ったのは、H - U・N・C・O。
実際他にもこれを思い出した人が多かったようだ。

本番、この問題と同様のデータ構造を作ろうと思ったが時間切れ。
ただ、後で聞いた解法がもっとシンプルだった。

円の右側のX軸との交点(X[i]+R[i])を小さい順に円をソートし、左側のX軸との交点(X[i]-R[i])が最長減少部分列になればよい。
最長減少部分列は、符号反転させれば最長増加部分列(LIS:Longest Increasing Subsequence)。
ちょうどTDPCの直前のCodeforceでLISのライブラリを作っていたので、それを使うだけ。

後は右側の交点が同じときのソート順に気を付ければよい。

int N;
pair<int,int> P[1000001];

vector<int> LIS(vector<int>& v) {
	int i;
	vector<int> dp(N,1<<30),id(N);
	FOR(i,v.size()) {
		id[i] = lower_bound(dp.begin(),dp.end(),v[i]) - dp.begin();
		dp[id[i]] = v[i];
	}
	int nl = *max_element(id.begin(),id.end());
	vector<int> ret(nl+1);
	FOR(i,N) if(id[N-1-i] == nl) ret[nl--] = v[N-1-i];
	return ret;
}

void solve() {
	int f,r,i,j,k,l, x,y,z;
	
	cin>>N;
	FOR(i,N) {
		cin>>x>>y;
		P[i]=make_pair((x+y),(x-y));
	}
	sort(P,P+N);
	vector<int> V;
	FOR(i,N) V.push_back(-P[i].second);

	vector<int> L=LIS(V);
	return _P("%d\n",L.size());
}

まとめ

LISはいろいろなところに使えそうだ。
UNCOのデータ構造はすぐに使いまわすのは難しいしな…。