kmjp's blog

競技プログラミング参加記です

Hello 2019 : E. Egor and an RPG game

うーん、まんまとはまった。
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に分割できる(らしい)。」って特徴は初めて知った。