kmjp's blog

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

Codeforces #658 Div1 B. Unmerge

なんか本番やたら苦労してるな。
http://codeforces.com/contest/1381/problem/B

問題

1~2NのPermutationがX与えられる。
このPermutationを2つの長さNの配列A,Bに分割したとする。
A,Bをマージソートの要領でマージしたとき、入力列に一致するような、A,Bの分割はあるか判定せよ。

解法

X[i...j]が降順にならんているとき、この部分はA,B同じ側に入らなければならない。
Xはこのような塊がいくつかあると考えると、それをちょうど合計Nずつになるように振り分ける問題になる。
あとはbitsetなどでナップサック問題を解けばよい。

int A;
int N;
int P[404040];

bitset<4040> F,T;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>A;
	while(A--) {
		cin>>N;
		FOR(i,2*N) cin>>P[i];
		vector<int> V;
		int cur=0;
		while(cur<2*N) {
			x=cur+1;
			while(x<2*N&&P[cur]>P[x]) x++;
			V.push_back(x-cur);
			cur=x;
		}
		
		F.reset();
		F[0]=1;
		FORR(c,V) {
			F|=F<<c;
		}
		if(F[N]) {
			cout<<"YES"<<endl;
		}
		else {
			cout<<"NO"<<endl;
		}
		
		
		
	}
}

まとめ

この回レート減少幅ひどかったな。