백준14832 Dice Straight (Large)

작성일 | In

문제 링크

  • http://icpc.me/14832

문제 출처

  • Google Code Jam 2017 World Finals A2

사용 알고리즘

  • 이분 매칭
  • 투포인터

시간복잡도

  • $O(N^2)$ per testcase

풀이

$O(N^4), O(N^3), O(N^2)$ 풀이를 차례대로 알아봅시다. 실제 대회에서는 $O(N^3)$ 풀이를 구현하면 10점, $O(N^2)$ 풀이를 구현하면 25점을 받을 수 있었습니다.

$O(N^4)$

각 주사위는 최대 한 개의 수를 표현하게 됩니다. 주사위가 하나의 수를 선택한다는 점에서 이분 매칭을 생각해볼 수 있습니다.
주사위의 집합 $L$, 한 번 이상 등장하는 수의 집합 $R$, 주사위와 그 주사위에 써있는 수를 연결한 간선 집합 $E$가 있을 때, 적당한 집합 $r \subset R$에 대해 이분 그래프 $G_r = (L, r, E)$의 최대 매칭을 구하는 문제로 환원할 수 있습니다.

적당한 집합 $r \subset R$의 원소를 모두 정렬하면 연속한 자연수가 되어야 하고, 정렬된 배열의 구간을 선택한다고 생각하면 $O(N^2)$ 가지의 구간을 생각할 수 있습니다.
$O(\vert L \cup r \vert \cdot \vert E \vert) = O(N^2)$ 이분 매칭을 $O(N^2)$번 수행하면 $O(N^4)$에 문제를 풀 수 있습니다.

$O(N^3)$

투포인터를 이용하면 $O(N)$개의 구간만 봐도 충분합니다.
현재 구간을 나타내는 $r$이 있을 때, 세 가지 케이스로 분류할 수 있습니다.

  1. $e \in R, e = \max(r) + 1$인 원소 $e$가 존재하지 않음
  2. $e$를 $r$에 추가했을 때 매칭의 개수가 증가
  3. 증가하지 않음

2번의 경우 구간의 끝점을 뒤로 1만큼 밀고, 3번의 경우에는 구간의 시작점을 1만큼 뒤로 당기면 됩니다.
마지막으로 1번의 경우에는 끝점을 뒤로 1만큼 밀고, 시작점을 끝점과 동일하게 만들어주면 됩니다.

총 $O(N)$개의 구간에 대해 $O(N^2)$ 이분 매칭을 수행하면 $O(N^3)$에 문제를 풀 수 있고, Dice Straight (Small) 문제에서 AC를 받을 수 있습니다.

$O(N^2)$

이제 구간의 개수를 더 줄이는 것은 불가능합니다. 이분 매칭을 어떻게 최적화할 수 있을까요?

투포인터에서 포인터의 이동 과정을 생각해봅시다.
끝점이 이동하면 최대 1만큼 유량을 더 흘리게 됩니다. 반대로, 시작점이 이동하면 최대 1만큼 유량을 제거하게 됩니다. 두 연산은 각각 $O(N)$번 수행하게 됩니다.

1만큼 유량을 흘리는 것은, 간선을 추가하고 DFS를 이용해 Augmenting Path를 찾아주는 것으로 $O(N)$에 수행할 수 있습니다.
유량을 1만큼 제거하는 것은, 제거하고자 하는 정점 $v \in r$에 대해, $v$와 매칭을 이루고 있는 정점 $u \in L$을 찾아서 두 정점 사이의 유량을 제거하면 됩니다. 이 과정도 $O(N)$에 수행할 수 있습니다.

따라서, 투포인터에서 시작점과 끝점이 각각 $O(N)$번 이동하고, 포인터가 이동할 때마다 유량의 변화를 $O(N)$에 계산할 수 있으므로 $O(N^2)$에 문제를 풀 수 있습니다.

본 대회의 시간 제한은 120초였지만 BOJ는 30초로 세팅되어 있어 상수 커팅이 필요할 수 있습니다.

전체 코드

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
#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using namespace std;

int N, A[50000][6], mp[1000001];
vector<int> C, G[300000], I[300000];

int P[50000], R[300000], V[50000], pv, match;
inline void addEdge(int s, int e){ G[s].push_back(e); }
bool dfs(int v){
    for(auto i : G[v]){
        if(V[i] == pv) continue; V[i] = pv;
        if(P[i] == -1 || dfs(P[i])){ P[i] = v; R[v] = i; return true; }
    }
    return false;
}
inline void insert(int x){
    for(auto i : I[x]) addEdge(x, i);
    pv++; match += dfs(x);
}
inline void erase(int x){
    if(R[x] != -1) match--, P[R[x]] = -1, R[x] = -1;
    G[x].clear();
}

void radixSort(){ // radix sort for coord compress
    static queue<int> Q[1024];
    for(auto i : C) Q[i & 1023].push(i);
    C.clear();
    for(int i=0; i<1024; i++) while(Q[i].size()) C.push_back(Q[i].front()), Q[i].pop();

    for(auto i : C) Q[i >> 10].push(i);
    C.clear();
    for(int i=0; i<1024; i++) while(Q[i].size()) C.push_back(Q[i].front()), Q[i].pop();
}

void Solve(){
    cin >> N;
    for(int i=0; i<N; i++) for(int j=0; j<6; j++) cin >> A[i][j], C.push_back(A[i][j]);
    radixSort(); C.erase(unique(all(C)), C.end());
    for(int i=0; i<C.size(); i++) mp[C[i]] = i;
    for(int i=0; i<N; i++) for(int j=0; j<6; j++) I[mp[A[i][j]]].push_back(i);

    match = 0;
    memset(P, -1, sizeof(int)*N);
    memset(R, -1, sizeof(int)*C.size());

    int l = 0, r = 0, mx = 0;
    insert(0);
    while(true){
        if(match == r-l+1) mx = max(mx, r-l+1);
        if(l+1 == C.size()) break;
        else if(r+1 == C.size()) erase(l++);
        else if(l == r || match == r-l+1){
            if(C[r]+1 != C[r+1]) while(l <= r) erase(l++);
            insert(++r);
        }
        else erase(l++), pv++, match += dfs(r);
    }
    cout << mx << "\n";

    for(int i=0; i<C.size(); i++) G[i].clear(), I[i].clear();
    C.clear();
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int T; cin >> T; C.reserve(50000*6);
    for(int tc=1; tc<=T; tc++){
        cout << "Case #" << tc << ": ";
        Solve();
    }
}