Codeforces #327 Div1 A. Median Smoothing

せっかくD解いたのにCの問題文誤読でレート落とした…。
http://codeforces.com/contest/590/problem/A

問題

0,1で構成されるN要素の数列A[1..N]が与えられる。
１回処理を行うと、各要素は周辺３要素の中間値になる。
すなわち

• 両端のA[1],A[N]は値が変化しない。
• それ以外、A[i]はA[i-1],A[i],A[i+1]の中間値になる。

Aに処理を繰り返したとき、値が変化しなくなるまで何回処理が必要か。
また変化しなくなった時の状態を求めよ。

解法

境界をA[0]=A[1]、A[N+1]=A[N]としておくと、A[1]・A[N]も特別扱いしなくてよくなる。
２つ以上同じ要素が連続している箇所は、中間値を取っても変化しない。
よって変化するのは10が交互に登場するケースである。

• 交互に登場する数値が奇数要素分の場合、以下のように両端の要素の数分の処理を行った後、その外側の連続成分と同じ要素になる。

00101010100
00010101000
00001010000
00000100000
00000000000

• 交互に登場する数値が偶数要素分の場合、以下のように要素数の半分の処理を行った後、半々でその外側の連続成分と同じ要素になる。

0010101011
0001010111
0000101111
0000011111

int N;
int A[505050],B[505050];
vector<pair<int,int> > V,V2;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>A[i];
	A[N]=A[N-1];
	V.push_back({A[0],1});
	FOR(i,N+1) {
		if(A[i]!=V.back().first) V.push_back({A[i],0});
		V.back().second++;
	}
	FORR(r,V) {
		if(V2.empty()) V2.push_back(r);
		else if(r.second>1) V2.push_back(r);
		else {
			if(V2.back().first<10) V2.push_back({r.first+10,1});
			else V2.back().second++;
		}
	}
	
	int ma=0;
	int cur=0;
	FORR(r,V2) {
		if(r.first<10) {
			FOR(i,r.second) B[cur++]=r.first;
		}
		else {
			ma=max(ma,(r.second+1)/2);
			if(r.second&1) {
				FOR(i,r.second) B[cur++]=(r.first-10)^1;
			}
			else {
				FOR(i,r.second/2) B[cur++]=(r.first-10)^1;
				FOR(i,r.second/2) B[cur++]=(r.first-10);
			}
		}
	}
	_P("%d\n",ma);
	FOR(i,N) _P("%d ",B[i+1]);
	_P("\n");
	
}

まとめ

750ptということでちょっとややこしい。