E

문제 설명 :

주어진 순열 a를 k만큼 오른쪽으로 민 순열을 b_k 라고 하자. (ex [1,2,3,4] 를 2만큼 민 결과 => [3,4,1,2]) 이 때 순열의 원소를 최대 m번 교환할 수 있다.

최대 m번을 교환해서 b_k 를 주어진 순열 a로 되돌릴 수 있는 k는 몇개인가?

문제 해설 :

이런 문제들이 다들 그렇듯이, 중요한 사실 몇 가지를 알고 있어야 문제를 푸는데 수월하게 풀 수 있다.

첫 번째는, 원소들을 교환해서 순열 a를 순열 b로 만드는 최소 횟수는 n개의 노드를 가진 무방향 그래프에서 모든 i에 대해 {a[i], b[i]} 간선을 추가했을 때의 컴포넌트 개수 c를 n에서 뺀 수와 같다 ( N - C )는 것이고, 두 번째는 최대 m개를 교환할 수 있으므로, 알맞은 위치에 있지 않은 수가 2m개를 넘는다면 그때의 k는 확인해 볼 필요도 없다는 것이다.

따라서, 각각 k마다 알맞은 위치에 있는 수의 개수를 미리 체크해주고, n-2m보다 체크가 많이 되어있는 k만 검사해보면 된다. 그러면 m<n/3이므로, 최대 3개만 검사하면 된다. 검사는 유니온 파인드로 했다.