Codeforces #189 Div1. B. Psychos in a Line

さてB。これは自力で解けたけどちょっと苦戦した。
http://codeforces.com/contest/319/problem/B

問題

1～Nの数列をpermuteしたものが与えられる。
この数列に対し、1ステップで手前の要素の方が大きい要素が削除される。
これ以上要素を削除できなくなるまでのステップ数を答えよ。

解法

問題の処理を愚直に実装するとO(N^2)かかってTLEする。
各数値A[i]が、自分の次にいる数字のインデックスB[i]を覚えておく。

各ステップにおいて、数列の各要素(A[i])からインデックスに格納された位置の数字を小さくなる限りたどっていき(B[i]、B[B[i]]、B[B[B[i]]]…とたどる)、その分の数値を削除すればよい。
実際に配列から削除すると重いので、インデックスを飛ばすことで対処する。

1ステップで1個ずつしか数値が減らないテストケースでは時間がかかるので、各ステップにおいてインデックスが変更した箇所を覚えておき、次のステップでは変更があった場所のみ処理する。

void solve() {
	int f,r,i,j,k,l, x,y;
	int N;
	vector<int> A,B,C,D;
	
	cin>>N;
	j=0;
	FOR(i,N) {
		A.push_back(GETi());
		B.push_back(i+1);
		if(i!=N-1) C.push_back(i);
	}
	
	y=0;
	while(!C.empty()) {
		D.resize(0);
		i=-1;
		FOR(j,C.size()) {
			k=C[j];
			if(k<i) continue;
			while(k<N && B[k]<N && A[B[k]]<A[k]) k=B[k];
			k=B[k];
			if(k!=B[C[j]]) D.push_back(C[j]);
			B[C[j]]=k;
			i=max(i,k);
		}
		if(D.empty()) break;
		y++;
		C=D;
	}
	cout << y << endl;
}

まとめ

うーん、説明がしにくい問題だな…。