[ABC 272] G. Yet Another mod M ★

문제 링크

백설공주와 난쟁이와 비슷한 것도 같다. 물론 안 풀어봤다.

아무튼 이 문제는 랜덤 알고리즘으로 푸는 문제이다.

처음 접하는 컨셉이라 신선하고 좋다.

문제 요약

길이 $N$의 정수 sequence $A$가 주어진다. 이 때 $A$의 각 원소는 distinct하다.

자연수 $M\in [3,10^9]$을 골라 모든 $A_i$에 대해 $\mathrm{mod\ } M$을 취해줬을 때,

$A$의 majority가 존재하게 하는 $M$을 찾아라.

제한

• $1\le N\le 5\ 000$
• $1\le A_i\le 10^9$

 

문제 풀이

Monte Carlo algorithm은 적당한 시간 내에 동작하지만, 확률적으로 정답을 구하지 못할 수 있는 알고리즘을 말한다. 시간이 충분히 빠르다면 여러 번 수행함으로서 정답을 구할 확률을 기하급수적으로 높일 수 있다.

확률을 고정(= 수행 횟수를 고정)하고서 시간 복잡도를 분석하면 되겠다. 그럼 ~의 확률로 ~시간에 답을 구하는 알고리즘이라고 하면 되겠다.

Las Vegas algorithm은 항상 정답을 구하지만, 수행 시간이 들쑥날쑥한 알고리즘을 말한다. 높은 확률로 효율적이게 만드는 것이 좋다. 혹은 데이터를 shuffle 해서 고른 분포를 가정한 뒤 수행할 수도 있다.

기하 분포의 기댓값을 이용하면 되겠다. 그럼 평균 ~시간에 답을 구하는 알고리즘이라고 하면 되겠다.

 

Solution 1

조건을 만족하는 $M$이 존재한다고 가정하자.

이에 따라 $X$를 연산을 적용한 $A$의 majority라고 하자.

그리고, $S$를 $A_i​\mathrm{\ mod}\ M=X$를 만족하는 $i$의 집합이라고 하자.

이들은 변수가 아닌 미지의 상수들임을 유의하자.

 

그러면 임의의 $i,j\in S$에 대해, $M\mid (A_i-A_j)$이다.

 

$i,j$를 $[1,N]$에서 무작위로 선택하자. 이 때, $i$와 $j$가 모두 $S$에 속할 확률은 적어도 $\frac 1 4$이다.

알고리즘이 결국 올바른 답을 출력할 확률을 $L$이라고 하자.

랜덤 시행을 $\log_{\frac 34}(1−L)$번 반복하면 된다. $L$을 $99.9$%로 정했다면 24번이다.

 

따라서, 문제가 $O(\log_{\frac 34}(1−L)×N\sqrt[3]{\max A}​)$ 시간에 풀릴 것이라고 기대할 수 있다.

소수만 고려해도 된다는 점을 이용하면 $O(\log_{\frac 34}(1−L)×N\log \max A​)$ 시간으로 줄일 수 있다.

사실 더 나아가서, $2\times 3\times 5\times \cdots 29 > 10^9 > 2\times 3\times 5\times \cdots 23$이므로 소인수의 종류의 최댓값 $\omega = 9$이다.

따라서 $O(\log_{\frac 34}(1−L)×N\times \omega)$라는 더 효율적인 시간 복잡도를 가진다는 것을 알 수 있다.

 

만약 충분히 랜덤 시행을 했음에도 그런 $M$이 존재하지 않으면, 존재하지 않는다고 출력하면 된다.

 

주의할 점이 있다: $M=2$인 경우는 고려하면 안 되는데, 그렇다고 $M=4$인 경우도 고려를 안 하게 되면 틀린다.

 

생각해보니까 $\log_{\frac 34}(1−L)$를 다르게 생각해볼 수도 있을 것 같다.

정답이 나올때까지 돌리는 알고리즘이라고 생각하면...

'$X:=$정답이 나오는 시점까지의 시행 횟수'라고 했을 때 $E[X]=\frac 1 {1/4}=4$니까 이걸 대체해서 써도 될 듯 하다...

 

코드

그럼 내가 작성한 코드를 바탕으로 시간 복잡도를 분석해보자. 약간 짬뽕된 것 같은데...

• $99.9$% 이상의 확률로 정답을 출력하는 알고리즘이다.
• 평균 시간 복잡도: $O(\omega \times N\times E[X])$
• 시간 복잡도: $O(\omega \times N\times \log_{\frac 34}(1−L))$

#include <bits/stdc++.h>
using namespace std; using ii = pair<int,int>; using ll = long long;
#define rep(i,a,b) for (auto i = (a); i <= (b); ++i)
#define dbg(x) cerr << #x << ": " << x << '\n'
#define siz(x) int((x).size())
#define Mup(x,y) x = max(x,y)
#define mup(x,y) x = min(x,y)

const int N = 5003;
int n, a[N];
vector<int> primes;

void precalc_primes() {
    bool sieve[31623] {0,};
    for (int x = 2; x < 31623; ++x) {
        if (sieve[x]) continue;
        primes.push_back(x);
        for (int u = 2*x; u < 31623; u += x) sieve[u] = 1;
    }
}

void check(int m) {
    if (m <= 2) return;
    unordered_map<int,int> c;
    rep(i,1,n) c[a[i]%m]++;
    for (auto [k,v] : c) if (v > n/2) {
        printf("%d", m);
        exit(0);
    }
}

int main() {
    scanf("%d", &n);
    rep(i,1,n) scanf("%d", &a[i]);
    precalc_primes();
    check(4);
    rep(r,1,24) {
        int i = rand()%n+1, j = rand()%n+1;
        int t = abs(a[i]-a[j]);
        for (int p : primes) {
            if (p*p > t) break;
            if (t%p) continue;
            while (t%p == 0) t /= p;
            check(p);
        }
        check(t);
    }
    puts("-1");
}

 

Solution 2

비슷한 방식으로 접근한다. 우선 $A$를 shuffle 하자.

인접한 원소의 차 $A_i-A_{i+1}$을 생각해보자.

모든 $i\in [1,N)$에 대해 $M\nmid (A_i-A_{i+1})$인 경우는 오직 $A_1,A_3,A_5,\ldots,A_N$만이 majority일 경우이다.

하지만 이러한 경우라도 $A_1-A_3$의 약수들을 따져주면 문제가 사라진다.

 

따라서 $O(\omega \times N^2)$ 시간에 deterministic 하게 정답을 구해줄 수 있다.

하지만 shuffle을 통해 확률적으로 고른 분포를 만들었으므로 $O(\omega \times E[X]\times N)$이다.

 

그럼 정리해보면:

• $100$%의 확률로 정답을 출력하는 알고리즘이다.
• 평균 시간 복잡도: $O(\omega \times N\times E[X])$
• 하지만 -1을 출력해야 하는, 즉 $M$이 존재하지 않는 입력이 들어오기 때문에 평균 말고 최악으로 봐야 할 것 같다.
• 시간 복잡도: $O(\omega \times N^2)$

 

코드는 생략한다.

 

결론

Solution 1은 평균 $O(\omega \times N\times E[X])$로 보는게 맞고,

Solution 2는 최악 $O(\omega \times N^2)$로 보는게 맞으므로,

Solution 1이 더 좋은 풀이라고 생각된다.

 

하지만 확률적으로 문제를 푸는 서로 다른 두 가지의 접근을 모두 알아가면 좋겠다.