yukicoder : No.1804 Intersection of LIS

どこかで見た気がするけど思い出せない。
https://yukicoder.me/problems/no/1804

問題

1～NのPermutation Pが与えられる。
Pにおける最長のLISを考えた場合、複数のLISが考えられるが、どのLISにも含まれる要素を求めよ。

解法

まず一般的なLISの手順で、
f(k) := Pのk個目までのprefixにおいて、P[k]を含む最長のLISの長さ
を求めておく。
次に以下を後ろから求める。
g(k) := f(k)がP全体の最長のLISの長さに等しいか、k＜jかつP[k]＜P[j]かるg(k)+1=g(j)となるjが存在するならTrue

g(k)=Trueとなるkは、最長のLISに含まれうることを示す。
もしf(k)が一致するkのうち、g(k)=Trueとなるものが1つしかないなら、それは最長のLISを構成するうえで必ず含まなければならない要素であり、問題の条件を満たす要素となる。

int N;
int P[302020];
int L[303030];
int O[303030];
set<int> cand[303030];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	
	FOR(i,N+2) O[i]=1<<30;
	
	int ma=0;
	FOR(i,N) {
		cin>>P[i];
		L[i]=lower_bound(O,O+N,P[i])-O;
		ma=max(ma,L[i]);
		O[L[i]]=P[i];
	}
	
	for(i=N-1;i>=0;i--) {
		if(L[i]==ma) {
			cand[L[i]].insert(P[i]);
		}
		else {
			if(cand[L[i]+1].lower_bound(P[i])!=cand[L[i]+1].end()) {
				cand[L[i]].insert(P[i]);
			}
		}
	}
	
	
	int inc=0;
	FOR(i,N) if(cand[L[i]].count(P[i])&&cand[L[i]].size()==1) inc++;
	cout<<inc<<endl;
	FOR(i,N) if(cand[L[i]].count(P[i])&&cand[L[i]].size()==1) cout<<P[i]<<" ";
	cout<<endl;
	
}

まとめ

Dilworthの定理を最近見たからかな？