AtCoder ARC #102 : F - Revenge of BBuBBBlesort!

考察ができれば実装は比較的容易なんだけどね。
https://beta.atcoder.jp/contests/arc102/tasks/arc102_d

問題

1～Nの順列を成す数列Pが与えられる。
連続する３要素が降順の場合、反転する、という動作を繰り返し、Pを昇順列にできるか。

解法

逆に、1～Nの昇順列から、連続する３要素が昇順の場合反転する、という動作を繰り返し元のPを生成できるか考えよう。

反転する際に位置が変わらない、３要素の真ん中を考える。
この真ん中に来る要素は、連続しないという特徴が重要である。
例えば昇順列ABCDEをBを中心に反転するとCBADEとなる。
この後、3番目の要素を中心に反転することはない。
今はBADと昇順ではないので反転できないし、ADEを先に反転させてCBEDAとしても真ん中のBEDは反転できない。

連続する要素が反転の中心にならないということは、反転の中心になる要素は一連の処理が値が変わらないということになる。
そこで、まずPと1～Nの昇順列を見比べ、位置が異なる値については、累積和などで反転の中心になる可能性のある要素を列挙しよう。
「反転の中心になる可能性のある要素」はP[i]=iでなければならないので、まずそれを反転する。

あとは、1つおきに並ぶ「反転の中心になる可能性のある要素」およびそれらの隣接要素毎のグループで考えよう。
「反転の中心になる可能性のある要素」の隣接要素は、「反転の中心になる可能性のある要素」の選択順により最終的に収まる場所は変わるものの、重要な特性として

• 一旦右に動いたら以後左には動けない
• 一旦左に動いたら以後右には動けない

という性質がある。ここから、右に動くもの同士、左に動くもの同士は相対的な位置を変更できない。
よって、「反転の中心になる可能性のある要素」の隣接要素を、左に移動したものと右に移動したものに分け、それぞれ相対的な位置が変化していないかチェックするとよい。

int N;
int A[303030];
int ma[303030];
int mi[303030];
int did[303030];

int proc(vector<int> cand) {
	if(cand.empty()) return 1;
	FORR(c,cand) if(A[c]!=c) return 0;
	
	int i;
	int L=-1,R=-1;
	for(i=cand[0]-1;i<=cand.back()+1;i+=2) {
		if(A[i]==i) return 0;
		if(A[i]<i) {
			if(R>A[i]) return 0;
			R=A[i];
		}
		else {
			if(L>A[i]) return 0;
			L=A[i];
		}
	}
	
	return 1;
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	for(i=1;i<=N;i++) {
		cin>>A[i];
		
		if(abs(i-A[i])%2==1) return _P("No\n");
		if(i<A[i]) {
			did[i+1]++;
			did[A[i]+1]--;
		}
		else {
			did[A[i]+1]++;
			did[i+1]--;
		}
	}
	
	vector<int> cand;
	for(i=1;i<=N;i++) {
		if(i>=2) did[i]+=did[i-2];
		if(did[i]) {
			if(did[i-1]) return _P("No\n");
			if(cand.size() && cand.back()+2!=i) {
				if(!proc(cand)) return _P("No\n");
				cand.clear();
			}
			cand.push_back(i);
		}
	}
	if(!proc(cand)) return _P("No\n");
	cout<<"Yes"<<endl;
	
}

まとめ

まぁ本番これ自力で考察できる気はしないな。