코드포스(Codeforces) D. Lucky Permutation

https://codeforces.com/contest/1768/problem/D

Problem - D - Codeforces

문제풀이

 

n개의 중복되지 않는 정수가 주어질때 정확히 한 개의 inversion이 존재하는 순열 만드는 (두 원소를 스왑)최소횟수 구하는 문제이다.

여기서 inversion이란 두 인덱스 i,j와 순열 p가 주어졌을때 $$i<j \, and \, p_{i} > p_{j}$$ 인 조건을 만족하는 경우를 뜻한다.

 

1. n개의 원소로 구성된 순열중에서 inversion이 1개로 구성된 순열의 경우의 수는 n-1이다.

 

inversion이 존재하지 않는 순열은

(1) < (2) < ... < (n-1) < (n) 인 경우로 유일하다.

 

위 순열에서 inversion이 한 번만 나타나려면

 

(2,1) < (3) < .... < (n-1) < (n) 

(1) < (3,2) < (4) < ... < (n-1) < (n)

.....

(1) < (2) < .... < (n-2,n-1) < (n)

(1) < (2) < .... < (n-2) < (n,n-1)

 

n-1 가지 인것을 알 수 있다.

 

2. inversion이 존재하지 않는 순열로 만드는 최소 횟수는 n - cycle_cnt

 

p = {3, 2, 4, 1, 6, 5} 에서 inversion이 존재하지 않는 순열로 만들기 위해 그래프로 표현하면 아래 그림과 같다.

빨간 간선은 self loop이고 파랑 간선은 그렇지 않은 간선을 표현한 것이다.

여기서 inversion이 존재 하지 않는 순열을 최소횟수로 구성하려면 (파랑 간선의 개수 - non_self_loop_cycle_cnt) 스왑이 필요하다.

 

cycle_cnt => (self_loop_cycle_cnt + non_self_loop_cycle_cnt)

파랑 간선의 개수 => (n - self_loop_cycle_cnt)

최소횟수 => (n - self_loop_cycle_cnt - non_self_loop_cycle_cnt) => n - cycle_cnt

 

결론: 1번과 2번 사실을 통해서 n-1개의 (inversion 1개로 구성된)순열을 만드는 최소횟수를 구해보면 된다.

 

1 <= k < n 을 만족하는 k에서 inversion이 존재 하지 않은 순열을 만들기 위해 (x)->(k) and (y)->(k+1) 간선을 이루는 x,y 정점이 존재할 것이다. 여기서 한 개의 inversion을 만들기 위해 (x)->(k+1) and (y)->(k)로 기존의 간선을 끊고 추가해주면 된다.

 

만약 inversion이 없는 그래프에서 정점k와 정점k+1이 같은 사이클에 형성되었을 경우 inversion 1개인 그래프로 바꿨을 경우에는 기존 1개의 사이클에서 2개의 사이클로 분리되기 때문에 n - (cycle_cnt+1) 스왑횟수가 필요하다.

반면 inversion이 없는 그래프에서 정점k와 정점k+1이 다른 사이클에 형성되었을 경우 inversion 1개인 그래프로 바꿨을 경우에는 각각 2개의 사이클에서 1개의 사이클로 합쳐지기 때문에 n - (cycle_cnt-1) 스왑횟수가 필요하다.

 

코드

#include<bits/stdc++.h>

using namespace std;

const int MAX_N = 2e5 + 5;

int n, p[MAX_N], out[MAX_N], id[MAX_N];

void dfs(int cur, int _id) {

   id[cur] = _id;

   if(id[out[cur]] == -1) dfs(out[cur], _id);

}

void solve()

{

   cin >> n;

   for(int i=1; i<=n; ++i) {

      cin >> p[i];

      out[i] = p[i];

      id[i] = -1;

   }

   int cycleCnt = 0;

   for(int i=1; i<=n; ++i) if(id[i] == -1) {

      cycleCnt++;

      dfs(i, i);

   }

   int ans = n - cycleCnt + 1;

   for(int i=1; i<n; ++i) {

      if(id[i] == id[i+1]) {

         ans = n - cycleCnt - 1;

         break;

      }

   }

   cout << ans << '\n';

}

int main()

{

   ios_base::sync_with_stdio(0), cin.tie(0);

   int tc;

   cin >> tc;

   while(tc--) {

      solve();

   }

   return 0;

}