Chokudai SpeedRun 002 : L - 長方形 β

これも普段より100pt高めな気がする。
https://atcoder.jp/contests/chokudai_S002/tasks/chokudai_S002_l

問題

N個の長方形があり、それぞれ縦横の長さが与えられる。
これらのうちいくつかを選択し、任意の順番で重ねていくことを考える。
その際後に置く長方形は、前に置く長方形の内部に収まりきるようにしたい。

なお、長方形は90度回転させてもよいが、底辺や横の辺は互いに平行でなければならない。
条件を満たす範囲で、最大でいくつ並べることができるか。

解法

大きい順でなく小さい順に並べることを考える。
まず、縦横の長さに対し 縦≦横 となるように先に90度回転させておく。

あとは(縦の短い順, 横の長い順)でソートすると、あとは横の長さに関しLISを求めるだけになる。

int N;
pair<ll,ll> P[202020];
int X[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>x>>y;
		if(x<y) swap(x,y);
		P[i].first=x;
		P[i].second=-y;
	}
	sort(P,P+N);
	int ma=0;
	FOR(i,202020) X[i]=1<<30;
	FOR(i,N) {
		x=-P[i].second;
		y=lower_bound(X,X+202020,x)-X;
		X[y]=x;
		ma=max(ma,y+1);
	}
	cout<<ma<<endl;
	
}

まとめ

αとかβとかつくとMOTHERを思い出す性質です。