AtCoder ARC #141 : C - Bracket and Permutation

Cまではそこそこの時間で解けたので、大怪我には至らず。
https://atcoder.jp/contests/arc141/tasks/arc141_c

問題

開き括弧と閉じ括弧N個ずつで構成された文字列Sがあったとする。
ここで、1～2NのPermutationである2つの数列P,Qが与えられる。

• Pは、S[P[i]]を順に並べた文字列が正しい括弧列となる辞書順最小の数列である。
• Qは、S[Q[i]]を順に並べた文字列が正しい括弧列となる辞書順最大の数列である。

条件を満たすSが存在するか判定し、存在するなら一例を答えよ。

解法

Pを小さい順にみて行ったとき、途中で未出の値の最小値よりも大きな値P[i]が現れた場合、S[P[i]]は開きカッコであることがわかる。
同様に、Pを大きい順、Qを小さい順、Qを大きい順に見ていくと、Sの多くが確定する。
実際には、これで確定しない場合、条件を満たすSはない。

Sを求めたら、実際にP,Qが条件を満たす数列か確認しておこう。
(P,Qが辞書順最小・最大でない場合があるため)

int N;
int P[404040],Q[404040];
string S;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,2*N) {
		cin>>P[i];
		P[i]--;
	}
	FOR(i,2*N) {
		cin>>Q[i];
		Q[i]--;
	}
	S.resize(2*N,'_');
	set<int> cand;
	FOR(i,2*N) cand.insert(i);
	FOR(i,2*N) {
		if(i==0||P[i]!=*cand.begin()) S[P[i]]='(';
		cand.erase(P[i]);
	}
	FOR(i,2*N) cand.insert(i);
	FOR(i,2*N) {
		if(i==0||Q[i]!=*cand.rbegin()) S[Q[i]]='(';
		cand.erase(Q[i]);
	}
	FOR(i,2*N) cand.insert(i);
	for(i=2*N-1;i>=0;i--) {
		if(i==2*N-1||P[i]!=*cand.rbegin()) S[P[i]]=')';
		cand.erase(P[i]);
	}
	FOR(i,2*N) cand.insert(i);
	for(i=2*N-1;i>=0;i--) {
		if(i==2*N-1||Q[i]!=*cand.begin()) S[Q[i]]=')';
		cand.erase(Q[i]);
	}
	
	FORR(c,S) if(c=='_') {
		cout<<-1<<endl;
		return;
	}
	set<int> O,C;
	int cur=0;
	FOR(i,2*N) {
		if(S[i]=='(') O.insert(i);
		if(S[i]==')') C.insert(i);
	}
	FOR(i,2*N) {
		if(cur) {
			x=(O.size()?*O.begin():1<<20);
			y=(C.size()?*C.begin():1<<20);
		}
		else {
			x=(O.size()?*O.begin():1<<20);
			y=1<<20;
		}
		if(P[i]!=min(x,y)) {
			cout<<-1<<endl;
			return;
		}
		if(x<y) {
			cur++;
			O.erase(O.begin());
		}
		else {
			cur--;
			C.erase(C.begin());
		}
	}
	FOR(i,2*N) {
		if(S[i]=='(') O.insert(i);
		if(S[i]==')') C.insert(i);
	}
	FOR(i,2*N) {
		if(cur) {
			x=(O.size()?*O.rbegin():-1);
			y=(C.size()?*C.rbegin():-1);
		}
		else {
			x=(O.size()?*O.rbegin():-1);
			y=-1;
		}
		if(Q[i]!=max(x,y)) {
			cout<<-1<<endl;
			return;
		}
		if(x>y) {
			cur++;
			O.erase(*O.rbegin());
		}
		else {
			cur--;
			C.erase(*C.rbegin());
		}
	}
	
	
	cout<<S<<endl;
	
}

まとめ

手間取ったけどなんとかそこそこの時間で解けてよかった。