うーん、まんまとはまった。
https://codeforces.com/contest/1097/problem/E
問題
1~NのPermutationが与えられる。
これを部分列に分割せよ。その際、各部分列はLISかLDSにすること。
なお、部分列の個数は必ずしも最小でなくてもよいが、1~NのどんなPermutationでもその値を超えないというkがあるので、k以下で済ませること。
解法
細かい説明はEditorialを参照することとして、まず問題のkはk(k+1)/2 ≧ Nである最小のkである。
よって、Permutationをそのようなk個以下に分割することを考えよう。
そうするとkを大よそ√(2N)個以下にする必要がある。
貪欲にLISとLDSの大きい方をとる…だと最悪2√N個になってしまい失敗する。
長さNのPermutationにおけるLISの長さを|LIS|とすると、この数列Nは|LIS|個以下のLDSに分割できる(らしい)。
よって|LIS|≧kなら|LIS|分を取り除き残りを再帰的に処理、|LIS|<kなら|LIS|個のLDSを構築しよう。
int N,ON; vector<vector<int>> R; vector<pair<int,int>> lis; vector<int> prelis; void hoge(vector<int>& V) { if(V.empty()) return; lis.clear(); prelis.resize(V.size()); int i,x; FOR(i,V.size()) { int x=lower_bound(ALL(lis),make_pair(V[i],0))-lis.begin(); if(x==lis.size()) lis.resize(x+1); lis[x]={V[i],i}; if(x==0) { prelis[i]=-1; } else { prelis[i]=lis[x-1].second; } } if(1LL*lis.size()*(lis.size()+1)/2>=V.size()) { vector<int> V2,ret; for(i=lis.size()-1;i>0;i--) { x=prelis[lis[i].second]; lis[i-1]={V[x],x}; } for(i=x=0;i<V.size();i++) { if(x<lis.size() && lis[x].second==i) { ret.push_back(V[i]); x++; } else { V2.push_back(V[i]); } } R.push_back(ret); hoge(V2); return; } set<pair<int,int>> S; vector<vector<int>> R2; reverse(ALL(V)); FORR(c,V) { auto it=S.lower_bound({c,0}); int x; if(it==S.begin()) { R2.resize(R2.size()+1); x=R2.size()-1; } else { it--; x=it->second; S.erase(it); } S.insert({c,x}); R2[x].push_back(c); } FORR(r,R2) { reverse(ALL(r)); R.push_back(r); } } void solve() { int i,j,k,l,r,x,y; string s; cin>>N; ON=N; while(N--) { cin>>x; vector<int> V(x); FOR(i,x) cin>>V[i]; R.clear(); hoge(V); cout<<R.size()<<endl; FORR(r,R) { cout<<r.size(); FORR(r2,r) cout<<" "<<r2; cout<<endl; } } }
まとめ
「長さNのPermutationにおけるLISの長さを|LIS|とすると、この数列Nは|LIS|個以下のLDSに分割できる(らしい)。」って特徴は初めて知った。