UnKoder #05 : Chairs in Circle

変数の制限により適切な解法が定まるね。
https://www.hackerrank.com/contests/unkoder-05/challenges/chairs-in-circle

問題

1～N番の人が円形に並んだ1～N番の椅子に座っている。
初期状態では、i番の椅子にはA[i]番の人が座っている。

隣接する椅子に座る人を入れ替える、という動作を何度か繰り返してi番目の椅子にはB[i]番の人が座っている、という状態を作り出したい。
最小何回入れ替えを行えば条件を満たせるか。

なお、与えられる状態は、最大N回以下で条件を満たせるものとする。

解法

最大N回で条件を満たせることは確定しているので、(N-1)回以下で条件を満たすケースを探そう。
(N-1)回以下しか入れ替えを行わないなら、A[i]とA[(i+1)%N]を入れ替えない、というようなiが1個は登場するはずである。

よって、A[i]とA[(i+1)%N]を入れ替えないと仮定すると、この問題は円系ではなく1列に並んだ人を並べ替える問題となり、バブルソートの入れ替え回数の要領で解ける。

Nが小さいので、バブルソートの入れ替え回数を愚直にO(N^2)掛けて求めても、固定するiの総当たりと合わせてO(N^3)で余裕で間に合う。

int N;
vector<int> A,B;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>x, A.push_back(x-1);
	FOR(i,N) cin>>x, B.push_back(x-1);
	
	int mi=N;
	FOR(i,N) {
		int num=0;
		
		int rev[51]={};
		FOR(x,N) rev[A[x]]=x;
		FOR(x,N) {
			FOR(y,x) if(rev[B[y]]>rev[B[x]]) num++;
		}
		
		mi=min(mi,num);
		
		A.push_back(A[0]);
		A.erase(A.begin());
		B.push_back(B[0]);
		B.erase(B.begin());
	}
	cout<<mi<<endl;
	
}

まとめ

「答えは N 以下であることが保証されている．」の1文をちゃんと読むことがカギ。