[백준 25323] 수 정렬하기, 근데 이제 제곱수를 곁들인 [UCPC 2022 예선] (Platinum V)

https://www.acmicpc.net/problem/25323

25323번: 수 정렬하기, 근데 이제 제곱수를 곁들인

 

• AB가 제곱수이고, AC가 제곱수이면 BC도 제곱수이다.
• 증명 : (A^2)BC가 제곱수고, 제곱수를 제곱수로 나누면 제곱수라는 사실로부터 자명하다.
• 반대로 AB가 제곱수이고, AC가 제곱수가 아니면, BC도 제곱수가 아니다. (증명은 위와 똑같이 하면 된다)
• -> 수열이 몇 개의 Disjointed Set으로 나뉘어, 각각의 집합 안에서는 교환이 가능하고 다른 집합의 원소들끼리는 교환이 불가능하다는 사실을 알 수 있다.
• 서로 다른 두 원소가 같은 집합에 속하느냐 다른 집합에 속하느냐를 알기 위해, 제곱수 판정 코드를 짜야 한다. 이는 내장 수학 함수로 가능하다.

constexpr bool is_squared(long long n) {
    double temp = std::sqrt(n);
    return temp == static_cast<int>(temp);
}

이진 탐색으로도 가능하다. 

constexpr bool is_squared(long long n, long long s = 0, long long e = (1LL << 31)) {
    if (e - s <= 1) {
        if (s * s == n or e * e == n) {
            return true;
        } else {
            return false;
        }
    }
    long long m = (s + e) / 2;
    if (m * m <= n) {
        return is_squared(n, m, e);
    } else {
        return is_squared(n, s, m);
    }
}

 

• 그러나 수열에 들어오는 수의 범위가 10^18인 관계로, AB가 제곱수인지 알기 위해서 A와 B를 곱한 다음 저 함수에 집어넣는 것은 불가능하다. 그러면 오버플로우가 난다.
• 한 가지 해결법은 __int128을 사용하는 것이다. 여기서는 다른 방법을 사용해 보자.
• AB가 제곱수이고 A에 소인수 p가 홀수 번 곱해져 있다면, B에서도 소인수 p가 홀수 번 곱해져 있다.
• AB가 제곱수이고 A에 소인수 p가 짝수 번 곱해져 있다면, B에서도 소인수 p가 짝수 번 곱해져 있다.
• 따라서 AB가 제곱수이고 A에 소인수 p가 홀수 번 곱해져 있다면, gcd(A, B)도 그렇고, 반대도 성립한다.
• 따라서 A / gcd(A, B)에는 소인수 p가 짝수 번 곱해져 있다.
• 이것이 모든 소인수 p에 대해 성립한다. 따라서 AB가 제곱수이면 A / gcd(A, B)는 제곱수이다.

 

• 반대로... A / gcd(A, B)가 제곱수이고 B / gcd(A, B)가 제곱수라면, 두 수의 곱도 제곱수이다. 따라서 AB는 제곱수이다.
• 이를 바탕으로 is_swappable(a, b) 함수를 구현할 수 있다.

constexpr bool is_swappable(long long a, long long b) {
    long long gcd = std::gcd(a, b);
    return is_squared(a / gcd) and is_squared(b / gcd);
}

 

• 첫 번째로 생각할 수 있는 구현은, Disjointed Set들을 미리 구해 놓고 그 set 안에서 정렬을 시도한 뒤 정렬이 끝났는지를 std::is_sorted로 확인하는 것이다. 안타깝게도 Disjointed Set들을 구하는 데는 최대 O(N^2)이 걸린다.
• 다른 구현을 시도해 보자. 주어진 수열이 정렬 가능하다면, 그 정렬 방법은 한 가지밖에 없다. 그리고 그 결과는 std::sort를 돌려서 얻을 수 있다.
• 따라서 std::sort를 돌린 다음, 있어서는 안 되는 교환이 있는지 확인하는 구현을 떠올릴 수 있다. 두 과정은 각각 O(NlogN), O(N)에 끝난다.
• 모든 교환이 가능한 교환이었다면, 모든 원소들은 교환을 통해 자기 자신의 자리로 돌아올 수 있어야 할 것이다. 따라서 자기 자신의 자리를 저장할 수 있는 구조체를 만든다.

struct Ai {
    long long val;
    int next;

    bool operator<(const Ai &rhs) const {
        return val < rhs.val;
    }
};

 

• 첫 번째로 이런 구현을 생각해볼 수 있다. 첫 번째 원소를 교환을 통해 자기 자신의 자리로 돌려보낸다. 첫 번째 원소가 자기 자신의 자리로 되돌아가고 대신 교환당한 원소가 첫 번째 자리로 온다. 이 원소도 자기 자신의 자리로 돌려보내고 그 자리에 있던 원소가 첫 번째 자리에 온다. (...) 이 과정을 반복해 모든 원소를 제자리로 돌려보낸다. 돌려보낼 수 없으면 false를 리턴한다.
• 다만 이렇게 구현을 하면 모든 원소들을 한 번씩 다 훑게 되는데, 생각을 약간 해 보면, 모든 원소에 대해서 자기 자신의 자리로 돌아갈 수 있는지 확인만 하고 실제로 교환을 안 해도 구현할 함수의 진리치는 같다는 사실을 알 수 있다. 이렇게 해도 모든 원소들을 한 번씩 다 훑는 것은 똑같기 때문이다.

bool is_possible_rearrange(Ai *v, int sz) {
    for (int i = 0; i < sz; ++i) {
        if (not is_swappable(v[i].val, v[v[i].next].val)) {
            return false;
        }
    }
    return true;
}