Codeforces Round #485(div2)- E 풀이

문제 : codeforces.com/contest/987/problem/E

Problem - E - Codeforces

 풀이참고 :  jeonggyun.tistory.com/125?category=737081

Codeforces Round #485 (Div. 2) 풀이

최근 에디토리얼을 보다가 그건 이문제와 유사하니 이것도 한번 풀어보라 해서 풀게된 문제.

길이가 n인 수열이 주어지고, 서로 다른 인덱스 i, j를 골라서 swap하는 연산을

petr 는 3 * n 번 수행

Um_nik 은 7 * n + 1번 수행 할 때,

임의의 수열이 주어질 때, 누가 만든 수열인지 출력하는 문제이다.

 

n = 1   => 3 * n = 3 (홀수) 7 * n + 1 = 8 (짝수)

n = 2   => 3 * n = 6 (짝수) 7 * n + 1 = 15 (홀수)

등.. 몇개의 n을 대입해보면,

petr와 Um_nik의 연산의 수의 패리티가 다르다는 것을 알 수 있다.

 

 

1) Inversion의 수를 이용한 방법

 

inversion의 수란 수열의 쌍 중에서 정렬이 되지 않은 모든 쌍의 개수이다.

앞의 연산을 수행함에 따라서, inversion의 수가 변화하게 되고, 좀 더 자세히 관찰해보면 inversion의 수의 비트의 변화가 생긴다.

n = 4 이고 수열이 (2, 1, 4, 3)으로 주어지면

원소 기준 (2,1) , (4, 3) 이렇게 2쌍의 inversion을 가진다.

inversion의 총 개수를 어떻게 새줄까??

이걸 좀더 풀어보면 inversion이란

 

배열 a와, 인덱스 i를 기준으로 볼 때,

1) 나보다 수열 인덱스 상으로 앞에 나온 원소이면서

2) a[i] 보다 큰 원소이다.

이 2가지 조건을 모두 만족하는 개수를 새주면 된다.

 

수열을 앞에서부터 차례대로 봐주면서 이를 바탕으로 update를 해주면, 1) 조건은 당연히 만족하게 된다.

이때 구간처리를 할 수 있는 자료구조인 새그먼트 트리를 이용해서(펜윅 트리, 머지소트 트리 등등도 가능)

seg[i] : 값 i를 가지는 원소의 개수로 지정해주면

 

1) 나보다 큰 원소의 개수를 segment tree상에서 구간 [ a[i] + 1,  n] 에 해당하는 값으로 얻을 수 있다.

2) 새그먼트 트리에 a[i]의 정보를 갱신해준다.

 

이 과정을 반복하면, 전체 inversion의 수를 얻을 수 있다. 새그먼트 트리의 update, query 연산 전부 logn이고,

이를 n번 반복하므로 전체 시간복잡도는 nlgn이다.

 

n이 짝수, 홀수 일때 각각 몇개를 직접 해보면 규칙을 찾을 수 있는데

n의 비트와 inversion의 수의 비트가 같을 경우 petr

그 외의 경우에 um_nik을 출력해주면 된다.

 

<코드>

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
const int MAX = 2e9;
const int N= 1e6+5;
int seg[2*N], a[N];
void update(int p, ll val) { // plus
    for (seg[p += N] += val; p > 1; p >>= 1)seg[p >> 1] = seg[p] + seg[p ^ 1];
}

ll query(int l, int r) { //[l,r]
    r++;
    ll ret = 0;
    for (l += N, r += N; l < r; l >>= 1, r >>= 1) {
        if (l & 1)ret += seg[l++];
        if (r & 1)ret += seg[--r];
    }
    return ret;
}
int n;
int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n;
    ll ninv = 0; // number of inversion
    for(int i =1; i <= n; i++){
        cin >> a[i];
        // 1) plus inversion
        ninv += query(a[i]+1,n);       
        // 2) update segtree
        update(a[i], 1);
    }

    if(ninv%2 == n%2) cout << "Petr\n";
    else cout << "Um_nik";
}

 

2) cyclic-permutation을 이용한 풀이

 

en.wikipedia.org/wiki/Cyclic_permutation

Cyclic permutation - Wikipedia

모든 수열은 cycle의 집합으로 이루어진다.

여기서 cycle 이란, 수열의 각각의 인덱스를 노드로 보고, i -> a[i]로 간선을 가진다고 했을 때, 그 그래프가 가지는 싸이클을 말한다.

 

 

위 수열은 위와 같이 각 싸이클을 이루는 index끼리의 집합으로 나누어지며, 그림으로 표현한 것은 아래와 같다.

연산을 할 때 마다, 수열의 cycle의 수의 변화가 생기기 때문에 처음 cycle의 수를 새주면 되고 이는 O(n)으로 구할 수 있다. 1번 풀이와 유사하게 비트가 달라진다는 점만 보면 된다.

 

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
const int MAX = 2e9;
const int N = 1e6+ 1;
int a[N];
int n;
int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n;
    int ans = 0;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }

    for(int i = 1; i <= n; i++){
        if(a[i] == -1)continue;
        int x = i;
        ans^=1;
        while(x != -1){
            int y = a[x];
            a[x] = -1;
            x = y;
        }
    }

    if(!ans)cout<<"Petr";
    else cout <<"Um_nik";
}

 

패리티 비트(짝,홀)이 다르다는 것은 굉장히 큰 단서이고 이 문제에서는 무조건 답이 petr, um_nik 둘중에 하나 인 것으로

단서를 얻었으면 좋았을 것이다