Codeforces #176 Div1. C. Main Sequence

こちらは自力で解けなかったのでEditorialを見て解く。
http://codeforces.com/contest/286/problem/C

問題

整数列に対して、以下をCorrectな整数列と定義する。

1. 空な整数列はCorrect。
2. ２つのCorrectな整数列を連結した整数列はCorrect。
3. Correctな整数列Aに対し、自然数vに対して{v, (Aの各要素), -v}の形の整数列はCorrect。

ここで、ある整数列に対し、その絶対値からなる整数列と、値が確実に負である値の位置が与えられる。
確実に負ではない要素は、正か負かわからない。
このとき、この元の整数列がCorrectになりうるか答える。
Correctになるなら、整数列の中身を示す。

解法

本番では、「Correctな整数列２つに２分割できるなら、メモ化再帰しながら２分割しよう」と思ったけど、これだとサイズNに対して部分整数列がO(N^2)あるので間に合わない。

Editorialを見た所、整数列を逆順に見ていって、スタック状に処理すればよいことが分かった。
スタックには、負である整数が詰まっている。

• 次の整数とスタックの最上位の絶対値が等しく、かつ次の整数が負でなくて良いなら、スタックの最上位を取り除く。これは次の整数に正、スタックの最上位に負を割り当てて定義3を適用するのに等しい。
• そうでない場合は、次の整数をスタックに積む。

整数列を処理し終わったとき、スタックが空ならCorrect。
途中スタックが空になっても処理を継続する当たり、定義2が適用されるね。
もちろんこの処理はO(N)。

int N,T;
int P[1000001];
int M[1000001];

void solve() {
	int f,r,i,j,k,l,x,y;
	ll t;
	
	N=GETi();
	FOR(i,N) P[i]=GETi();
	T=GETi();
	FOR(i,T) M[GETi()-1]=1;
	
	stack<int> S;
	for(i=N-1;i>=0;i--) {
		int v=P[i];
		
		if(S.empty() || S.top()!=v || M[i]==1) {
			P[i]=-P[i];
			S.push(v);
		}
		else {
			S.pop();
		}
	}
	
	if(S.empty()) {
		_P("YES\n");
		FOR(i,N) _P("%d ",P[i]);
		_P("\n");
	}
	else {
		_P("NO\n");
	}
	
	return;
}

まとめ

スタックを用いた構文解析っぽいな。
逆順にするのがちょっとわかりにくい。