백준15064 Marblecoin

작성일 | In

문제 링크

  • http://icpc.me/15064

사용 알고리즘

  • 해싱

시간복잡도

  • $O(X \log N \log X)$

풀이

순서를 정하는 문제이므로 Exchange Argument를 이용한 그리디 알고리즘을 생각해봅시다.

두 수열 $A, B$가 있을 때 어떤 것을 먼저 사용해야 할까요? 만약 두 수열의 첫 원소가 다르다면 첫 원소가 작은 수열을 먼저 사용하는 것이 이득입니다. 그렇지 않을 경우, 사전순으로 빠른 것, 한 문자열이 다른 문자열을 Prefix로 갖는다면 길이가 긴 것을 사용하는 것이 이득입니다.

앞에 있는 원소가 제거되는 상황에서 두 수열의 사전순 비교를 하는 것은 해싱을 이용해 전처리 $O(\vert S \vert)$, 비교는 $O(\log \vert S \vert)$에 할 수 있습니다. 수열들을 Heap으로 관리하면 문제를 $O(X \log N \log X)$에 해결할 수 있습니다. 이때 $X$는 모든 수열의 길이의 합입니다.

전체 코드

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

using uint = unsigned;
using ll = long long;
using ull = unsigned long long;
constexpr ll MOD = 1e9+7;

template<ll P, ll M> struct Hashing {
    vector<ll> H, B;
    void build(const vector<int> &S){
        H.resize(S.size()+1);
        B.resize(S.size()+1);
        B[0] = 1;
        for(int i=1; i<=S.size(); i++) H[i] = (H[i-1] * P + S[i-1]) % M;
        for(int i=1; i<=S.size(); i++) B[i] = B[i-1] * P % M;
    }
    ll sub(int s, int e) const {
        s++; e++;
        ll res = (H[e] - H[s-1] * B[e-s+1]) % M;
        return res < 0 ? res + M : res;
    }
};
constexpr int P1 = 917, M1 = 1'000'000'007;
constexpr int P2 = 719, M2 = 1'000'000'009;

int N, K;
vector<int> A[101010];
Hashing<P1, M1> H1[101010];
Hashing<P2, M2> H2[101010];

struct Container {
    int use, len, idx;
    void build(int i){
        idx = i;
        H1[i].build(A[i]);
        H2[i].build(A[i]);
        use = 0; len = A[i].size();
    }
    pair<int, int> get(int l, int r) const {
        return { H1[idx].sub(l, r), H2[idx].sub(l, r) };
    }
    pair<int, int> prefix(int l) const { return get(use, use+l-1); }
    int size() const { return len - use; }
    bool empty() const { return size() == 0; }
    int front() const { return A[idx][use]; }
    const int& operator [] (int i) const { return A[idx][use+i]; }
    bool operator < (const Container &t) const {
        if(empty()) return false;
        if(t.empty()) return true;
        if(front() != t.front()) return front() < t.front();
        int l = 1, r = min(size(), t.size());
        while(l < r){
            int m = l + r >> 1;
            if(prefix(m) != t.prefix(m)) r = m;
            else l = m + 1;
        }
        int a = this->operator[](r-1), b = t[r-1];
        if(a == b) return size() > t.size();
        return a < b;
    }
    bool operator > (const Container &t) const {
        if(empty()) return true;
        if(t.empty()) return false;
        if(front() != t.front()) return front() > t.front();
        int l = 1, r = min(size(), t.size());
        while(l < r){
            int m = l + r >> 1;
            if(prefix(m) != t.prefix(m)) r = m;
            else l = m + 1;
        }
        int a = this->operator[](r-1), b = t[r-1];
        if(a == b) return size() < t.size();
        return a > b;
    }
};

Container H[101010];

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N;
    for(int i=1; i<=N; i++){
        int l; cin >> l; A[i].resize(l);
        for(auto &j : A[i]) cin >> j;
        H[i].build(i);
        K += l;
    }
    priority_queue<Container, vector<Container>, greater<>> pq(H+1, H+N+1);
    ll ans = 0;
    while(pq.size()){
        auto now = pq.top(); pq.pop();
        ans = (ans * 365 + now[0]) % MOD; now.use++;
        if(!now.empty()) pq.push(now);
    }
    ans = ans * 365 % MOD;
    cout << ans;
}