백준25492 전깃줄 연결

작성일 | In

문제 링크

  • https://icpc.me/25492

사용 알고리즘

  • 유클리드 호제법
  • 세그먼트 트리
  • 스파스 테이블

시간복잡도

  • $O(N \log N \log^2 C)$

풀이

점화식은 어렵지 않게 떠올릴 수 있습니다. $B$를 자신의 누적 합 배열이라고 재정의하면, $D_i = \min\left{ D_j + C_i + C_j + B_{i-1} - B_j - 2 \times \gcd(C_j, \cdots, C_i) \right}$입니다. $i$에 대한 식을 밖으로 빼면 $D_i = \min\left{ D_j + C_j - B_j - 2 \times \gcd(C_j, \cdots, C_i) \right} + C_i + B_{i-1}$처럼 바꿀 수 있습니다.
Sparse table을 이용해 구간의 gcd를 $O(\log C)$ 시간에 구한다고 해도 점화식을 계산하는 시간 복잡도는 $O(N^2 \log C)$입니다. 더 빠르게 계산하는 방법을 생각해야 합니다.

일단 구간의 gcd는 스파스 테이블을 이용해 구합시다. $O(N \log N \log C)$ 시간 전처리를 통해 구간 gcd 쿼리를 $O(\log C)$ 시간에 처리할 수 있습니다.

gcd는 좋은 성질을 몇 가지 갖고 있습니다. $\gcd(a, b) \leq \min(a, b)$이고, 만약 $\gcd(a, b) \neq \min(a, b)$라면 $\gcd(a, b) \leq \min(a, b) / 2$입니다. 즉, gcd 연산을 수행해도 값이 커지지 않고, 만약 값이 변했다면 항상 절반 이하로 감소합니다. 따라서 어떤 수열의 prefix gcd는 최대 $O(\log C)$번 바뀝니다.

이 성질을 이용하면 세그먼트 트리를 이용해 점화식을 빠르게 계산할 수 있습니다. 구체적으로, $D(i)$를 계산해야 하는 시점에 세그먼트 트리의 $i$번째 리프 정점에서 $\min\left{D_j + C_j - B_j - 2\times \gcd(C_j, \cdots, C_i)\right}$를 관리할 것입니다.
이렇게 점화식을 계산하기 위해서는, $D(i)$를 구한 다음에 $i$보다 큰 지점 $k$에 $D(i) + C(i) - B(i) - 2 \times \gcd(C_i \cdots, C_k)$를 갱신해야 합니다. $O(N)$개의 지점에 개별적으로 갱신을 해야 할 것 같지만, prefix gcd가 최대 $O(\log C)$번 바뀐다는 사실을 이용하면 $O(\log C)$번의 range update를 이용해 갱신할 수 있습니다. 따라서 각 $i$마다 세그먼트 트리에 point query와 range update를 수행하는데 걸리는 시간은 $O(\log N + \log N \log C)$입니다.

이제 서로 다른 $O(\log C)$개의 gcd값과 그 구간을 구하기만 하면 됩니다. gcd값이 바뀌는 구간의 경계는 파라메트릭 서치를 이용해 쉽게 찾을 수 있습니다. $O(\log C)$개의 구간을 찾기 위해 매번 이진 탐색을 수행하면, 스파스 테이블에 구간 gcd 쿼리를 총 $O(\log N \log C)$번 날리게 됩니다. 따라서 모든 구간을 찾는데 걸리는 시간은 $O(\log N \log^2 C)$입니다.

전체 시간 복잡도는 $O(N \log N \log^2 C)$입니다.

전체 코드

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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr int SZ = 1 << 18;

ll N, A[202020], B[202020], D[202020];
ll P[18][SZ], T[SZ << 1];

ll GCD(int l, int r){
    int k = __lg(r-l+1);
    return __gcd(P[k][l], P[k][r-(1<<k)+1]);
}

void Update(int l, int r, ll v){
    l |= SZ; r |= SZ;
    while(l <= r){
        if(l & 1) T[l] = min(T[l], v), l++;
        if(~r & 1) T[r] = min(T[r], v), r--;
        l >>= 1; r >>= 1;
    }
}

ll Query(int x){
    x |= SZ; ll res = T[x];
    while(x >>= 1) res = min(res, T[x]);
    return res;
}

vector<pair<ll, ll>> Get(int s){
    vector<pair<ll, ll>> res;
    for(int e=s+1; e<=N; ){
        ll g = GCD(s, e);
        int l = e, r = N;
        while(l < r){
            int m = (l + r + 1) / 2;
            if(GCD(s, m) == g) l = m;
            else r = m - 1;
        }
        res.emplace_back(l, g);
        e = l + 1;
    }
    return res;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N;
    for(int i=1; i<=N; i++) cin >> A[i];
    for(int i=1; i<=N; i++) cin >> B[i];

    for(int i=1; i<=N; i++) P[0][i] = A[i];
    for(int i=1; i<18; i++) for(int j=1; j+(1<<i)-1<=N; j++) P[i][j] = __gcd(P[i-1][j], P[i-1][j+(1<<(i-1))]);

    memset(T, 0x3f, sizeof T);
    for(int i=1; i<=N; i++) B[i] += B[i-1];
    D[1] = 0;

    for(int i=1; i<=N; i++){
        if(i != 1) D[i] = Query(i) + B[i-1] + A[i];
        auto range = Get(i);
        int lst = i;
        for(auto [j,g] : range) Update(lst+1, j, D[i] + A[i] - B[i] - 2*g), lst = j;
    }
    cout << D[N];
}