Problem F 풀이 (C++)

 문제 링크 : https://codeforces.com/contest/1547/problem/F

이 문제를 풀기 위해 알아야 할 정보는 gcd(gcd(a,b),gcd(b,c)) = gcd(a,b,c) 라는 것이다.

이 정보에 따르면 결국 길이 n의 배열 a를 k번 변환했을 때,

ai = gcd(ai, ai+1, ai+2, ..., ai+k) 가 된다.

답을 찾기 위해서는 배열 a의 모든 원소가 같아지는 시점을 찾아야 한다.

이 작업을 있는 그대로 실행한다면 시간이 너무 오래 걸린다.

이를 해결하기 위해 세그먼트 트리와 이분 탐색을 이용한다.

세그먼트 트리는 여러 개의 데이터가 연속적으로 존재할 때 특정한 범위의 데이터의 합을 구하는 경우에 많이 사용된다.

이 문제의 경우 특정 구간의 부분 gcd를 구해야 하는 경우가 많기 때문에 사용한다.

세그먼트 트리를 구간의 gcd 값으로 구성하고 배열 a를 변환하는 횟수 k를 이분 탐색으로 찾는다.

세그먼트 트리를 만들 때 구간의 범위를 a0 ~ an-1까지가 아니라, 

a0 ~ an, a0, a1, ~~ an-2 까지 고려해야 한다는 점을 유의해야 한다.

이유는 배열 a는 최대 n번까지 변환 가능하고 그렇기 때문에 배열 a의 마지막 원소 an-1의 부분 gcd 값의 최대 범위는 gcd(an-1, a0, a1, ..., an-2)가 되기 때문이다.

이분 탐색 과정에서 확인해야 할 작업은 배열 a의 모든 원소 ai에 대해 부분 gcd를 확인하여 모두 같은지를 확인하는 것이다.

여기서 부분 gcd는 각 원소마다 gcd(ai, ai+1, ..., ai+k)이고 세그먼트 트리에서 탐색한다.

세그먼트 트리를 사용할 경우 구간의 부분 gcd를 구할 때마다 걸리는 시간은 O(logn) 시간이다.

이분 탐색에서 한번 확인하는 과정은 배열의 각 원소마다 부분 gcd를 구하는데 시간이 필요하고, 이 시간은 n x logn = O(nlogn)이 된다.

이분 탐색 과정은 O(logn)이므로 총 O(nlognlogn) 시간 복잡도가 나온다.

( 세그먼트 트리를 구성하는데 걸리는 시간은 계산해보니 약 O(2n)이 나왔다. )

이 문제에서 n의 최댓값은 20만이기 때문에 logn은 최대 18보다 작고 총 시간 복잡도는 제한 시간을 넘지 않는다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <math.h>
 
using namespace std;
 
int getGCD(int a, int b) {
    if (a > b)
        swap(a, b);
    if (a == 0)
        return b;
    while (b % a != 0) {
        b %= a;
        swap(a, b);
    }
    return a;
}
 
void initTree(vector<int>& tree, vector<int>& a, int index, int s, int e) {
    if (s == e) {
        tree[index] = a[s];
    }
    else {
        int m = (s + e) / 2;
        initTree(tree, a, index * 2 + 1, s, m);
        initTree(tree, a, index * 2 + 2, m + 1, e);
        tree[index] = getGCD(tree[index * 2 + 1], tree[index * 2 + 2]);
    }
}
 
int findGCD(vector<int>& tree, int index, int l, int r, int s, int e) {
    
    if (l > e || r < s) {
        return 0;
    }
    
    if (l <= s && e <= r) {
        return tree[index];
    }
 
    int m = (s + e) / 2;
    return getGCD(findGCD(tree, index * 2 + 1, l, r, s, m), findGCD(tree, index * 2 + 2, l, r, m + 1, e));
 
}
 
bool check(vector<int>& tree, vector<int>& a, int n, int num) {
 
    set<int> s;
    
    for (int i = 0; i < n; i++) {
        s.insert(findGCD(tree, 0, i, i + num, 0, a.size() - 1));
    }
 
    if (s.size() == 1)
        return true;
    else
        return false;
}
 
int main() {
 
    int t;
    cin >> t;
 
    while (t--) {
 
        int n;
        cin >> n;
 
        vector<int> a(n);
 
        for (int i = 0; i < n; i++)
            cin >> a[i];
 
        for (int i = 0; i < n - 1; i++)
            a.push_back(a[i]);
 
        int height = (int)(ceil(log2(a.size())));
        int size = 2 * (int)pow(2, height) - 1;
 
        vector<int> segTree(size);
 
        initTree(segTree, a, 0, 0, a.size() - 1);
 
        // binary search
        int s = 0, e = n - 1, m;
        int answer = n - 1;
 
        while (s <= e) {
            m = (s + e) / 2;
            if (check(segTree, a, n, m) == true) {
                e = m - 1;
                if (answer > m)
                    answer = m;
            }
            else
                s = m + 1;
        }
 
        cout << answer << endl;
    }
 
    return 0;
}
cs

댓글

댓글 쓰기