AtCoder AGC #014 : F - Strange Sorting

考察は重いし思いつかないけど、コードは短い。
http://agc014.contest.atcoder.jp/tasks/agc014_f

問題

1～Nの順列である整数列Pを考える。
以下の処理を、Pが完全に昇順になるまで繰り返すと何回かかるか。

• 空数列A,Bに対し、以下の処理を各iに対し順に行う
  • P[i]がP[0...i]中で最大ならP[i]をAの末尾に、そうでないならBの末尾に追加する
• PをBのあとAを連結したもので置き換える。

解法

スコアが高いだけあって考察が辛いので、細かい考察・証明はEditorialを参照。
以下解法のみ書く。

以下の2値を考える。
T(i) := P中で値i～Nの要素が昇順になるまでの最小処理回数
F(i) := T(i)が正の場合に定義される。(T(i)-1)回処理を行った段階で、i～NのうちP中で最も手前にある値。(F(i)＞iである。)

このT,Fは大きい順に求められる。
T(N)=0は明らかなので、T(N-1)から順に求めていこう。

• T(i+1)=0の場合
  • P中でiが(i+1)の手前にあるならすでにi～Nも昇順なのでT(i)=0
  • そうでなければ、1回処理を行えばiが(i+1)の手前に来るのでT(i)=1、F(i)=i+1
• T(i+1)＞0の場合
  • i、(i+1)、F(i+1)の並び順を考える。
  • 細かい証明は省くが、i、(i+1)、F(i+1)がP中この順、または巡回された順である場合、T(i)=T(i+1)、F(i+1)=F(i+1)である。
  • そうでない場合、T(i)=T(i+1)+1、F(i)=i+1となる。

i、(i+1)、F(i+1)がこの順であるケースはまだしも、「巡回された順」っていう部分は理解が難しい。
T(i)=T(i+1)である場合、この３値の順は巡回することはあっても逆順になることはないらしい。
逆にT(i)=T(i+1)+1の場合と、この順の反転が同義となる。

int N;
int A[202020];
int B[202020];
int T[202020],F[202020];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>A[i];
		B[A[i]]=i+1;
	}
	
	T[N]=0;
	F[N]=N;
	for(i=N-1;i>=1;i--) {
		if(T[i+1]==0) {
			if(B[i]<B[i+1]) {
				T[i]=0;
				F[i]=i;
			}
			else {
				T[i]=1;
				F[i]=i+1;
			}
		}
		else {
			if((B[F[i+1]]<B[i] && B[i]<B[i+1]) || (B[i]<B[i+1] &&  B[i+1]<B[F[i+1]]) || (B[i+1]<B[F[i+1]] && B[F[i+1]]<B[i])) {
				T[i]=T[i+1];
				F[i]=F[i+1];
			}
			else {
				T[i]=T[i+1]+1;
				F[i]=i+1;
			}
		}
	}
	cout<<T[1]<<endl;
	
}

まとめ

こんなの思いつかないなぁ。