yukicoder : No.1425 Yet Another Cyclic Shifts Sorting

これ系Codeforcesに多い印象。
https://yukicoder.me/problems/no/1425

問題

N要素の整数列Aが与えられる。
この数列に対し、先頭x要素をrotateする、という処理を繰り返しAを昇順にしたい。
最少xを何通り準備すれば目的を達成できるか。

解法

xとして2とNの2つを準備すれば、任意の位置の隣接要素をswapできることになるので、当然ソートもできる。
よって解の上限は2。
元々ソートされてれば0なので、あとはxが1通りになるかどうかを判定しよう。

int N;
int A[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	multiset<int> S;
	FOR(i,N) {
		cin>>A[i];
		S.insert(A[i]);
	}
	while(N && A[N-1]==*S.rbegin()) {
		S.erase(S.find(A[N-1]));
		N--;
	}
	if(N==0) return _P("0\n");
	
	int mi=*min_element(A,A+N);
	x=0;
	FOR(i,N) if(A[(i+N-1)%N]>A[i]) x=i;
	FOR(j,N-1) if(A[(x+j)%N]>A[(x+j+1)%N]) break;
	if(j==N-1) cout<<1<<endl;
	else cout<<2<<endl;
}

まとめ

実は上限が小さいっての、Codeforcesでたまにある印象。