블로그 옮겼습니다

Codeforces Round #377 (Div. 2) E. Sockets 본문

Algorithm/Problem Solving

Codeforces Round #377 (Div. 2) E. Sockets

sgc109 2017. 7. 30. 00:38

http://codeforces.com/contest/732/problem/E


N <= 2 * 10^5

M <= 2 * 10^5


컴퓨터 N대와 소켓 M개가 있다. 소켓과 컴퓨터를 매칭 시키고 싶다.

xi <= 10^9 컴퓨터의 전압 N개와

yi <= 10^9 소켓의 전압 M개가 입력으로 주어진다.

어댑터를 하나 사용하면 소켓의 전압을 절반으로 낮출 수 있다.(홀수인 경우엔 1더하고 반으로나눔)

xi 와 yj 를 같게 만들면 매칭을 시킬 수가 있다. 이 때 최대 매칭 수를 구하고 싶은데

이 때 사용하는 어댑터 수를 최소화 해야한다. 이 때 총 매칭수, 총 사용한 어댑터수,

각 소켓에 사용되는 어댑터의 수, 각 컴퓨터와 매칭되는 소켓의 번호 를 출력하는 문제이다.


우선 O(Nlg^2N) 풀이를 말하자면 

되게 직관적인 풀이이다. 컴퓨터와 소켓을 정렬된 상태로 유지하면서 둘의 맨 끝놈 둘만

비교하여 같으면 매칭시켜주고 다르면 대소 관계에 따라 포인터를 이동시켜주거나 소켓에 어댑터를

써주거나 하는것이다.

전압을 1순위로(오름차순), 사용한 어댑터 수를 2순위로(내림차순) 정렬되어있는 pq를 선언하여

소켓들을 모두 넣어주고, 컴퓨터를 전압으로 오름차순 정렬해준다.

컴퓨터를 맨 뒤에서 부터 보는 포인터를 하나 둔다.

현재 포인터가 가리키는 컴퓨터와 pq의 top과 비교하여 

대소관계에 따라 top에 어댑터를 하나 써서 다시 push 혹은 포인터-- 혹은

둘이 같다면 pq.pop(), 포인터--모두하며 답을 갱신 하는 과정을 반복한다.

pq 의 top을 어댑터로 반씩 줄이는데에 log 가 들고 또 힙 삽입 삭제에 log 가 들어서

O(Nlg^2N) 이다.


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
#include <bits/stdc++.h>
#define pb push_back
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
#define fastio() ios_base::sync_with_stdio(0),cin.tie(0)
using namespace std;
typedef long long ll;
const int MOD = 1e9+7;
const int INF = 0x3c3c3c3c;
const long long INFL = 0x3c3c3c3c3c3c3c3c;
 
struct sock{
    int volt, used, id;
    bool operator<(const sock& rhs) const{
        if(volt != rhs.volt) return volt < rhs.volt;
        if(used != rhs.used) return used > rhs.used;
        return id < rhs.id;
    }
};
struct com{
    int volt, id;
    bool operator<(const com& rhs) const{
        if(volt != rhs.volt) return volt < rhs.volt;
        return id < rhs.id;
    }
};
priority_queue<sock> pqS;
priority_queue<com> pqC;
int N, M, a;
int C, U;
int A[200003], B[200003];
int main() {
    fastio();
    cin >> N >> M;
    for(int i = 1 ; i <= N; i++) {
        cin >> a;
        pqC.push(com{a, i});
    }
    for(int i = 1 ; i <= M; i++) {
        cin >> a;
        pqS.push(sock{a, 0, i});
    }
 
    while(!pqS.empty() && !pqC.empty()){
        auto endS = pqS.top();
        auto endC = pqC.top();
        if(endS.volt < endC.volt) pqC.pop();
        else if(endS.volt == endC.volt){
            C++;
            U += endS.used;
            A[endS.id - 1= endS.used;
            B[endC.id - 1= endS.id;
            pqC.pop();
            pqS.pop();
        }
        else {
            pqS.pop();
            pqS.push(sock{(endS.volt + 1/ 2, endS.used + 1, endS.id});
        }
    }
 
    cout << C << " " << U << "\n";
    for(int i = 0 ; i < M; i++cout << A[i] << " ";
    cout << "\n";
    for(int i = 0 ; i < N; i++cout << B[i] << " ";
    return 0;
}
cs



이 것을 O(NlgN) 으로 줄이기 위해 캐치해야될 중요한 것들이 있다.

우선 전압이 작은 소켓부터 어댑터를 써가며 가장 먼저 매칭 가능한 컴퓨터와

매칭해버리는게 무조건 최적이라는 것을 알아 채야한다.

말로써 증명을 한 번 해보자. 만약 소켓 s1에 어댑터를 써가며 가장 먼저 매칭 가능한 컴퓨터 c2가

있다고 해보자. 그럼 만약 s1가 s2를 전압이 더 큰 소켓 s2에게 양보를 한다고 해보자.

일단 양보를 한다는 것은 s2도 어댑터를 몇개를 사용하던 어쨌든 어댑터를 사용하면 c2와

전압이 같아질 수 있다는 것인데 그렇다면 전압이 c2 이하인 컴퓨터들에 대해서는

매칭 가능한 집합이 s1와 s2는 완벽하게 일치하기 때문에 만약 s1가 s2에게 c2를 양보하고

어떤 다른 컴퓨터 c1과 매칭 가능하다면 s2도 c1과 매칭 가능한 것이며 좀만 생각해보면

이 때 s1와 s2에 사용되는 어댑터 수의 합은 결국 똑같기 때문에 굳이 양보하지 않아도

됨을 알 수가 있다. 그리고 애초에 c1이 존재하지 않는다면 굳이 전압 차이가 더 큰 s2 에게 양보해서

c2와 매칭시키기 위해 사용하는 어댑터만 많아져 딱히 득이 없음을 알 수가있다.

게다가 s2는 어댑터를 써갈 때 가장 먼저 매칭가능한 컴퓨터가 c2가 아닐 수가 있다.

그니까 s1과 매칭 시킬 수 있는 컴퓨터들의 집합이 s2과 매칭 시킬 수 있는 컴퓨터들의 집합의

부분 집합이라는 것을 알 수가 있게 된다. 그래서 s1가 s2에게 c2를 양보함으로써 오히려

총 매칭 수가 줄어들 수가 있는 것이다.


그럼 이걸 구현을 해보자. 소켓을 정렬하고 앞에서부터 하나씩 어댑터를 써가며

컴퓨터와 매칭을 시킬 수도 있겠고, M개의 소켓에 대해 일괄적으로 어댑터를 한번씩 써가면서

투 포인터로 앞에서 부터 O(N + M) 에 컴퓨터와 소켓을 매칭 시켜주고

매칭된 컴퓨터와 소켓의 인덱스는 배열에 체크를 해주는식으로 구현할 수도 있을 것이다. 개인적으로 전자는

좀더 직관적이기는 하나 O(NlgN) 으로 하기 쉽지가 않았고 후자가 STL사용이 훨씬 덜 복잡해서

구현하기는 더 쉬웠다.


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
#include <bits/stdc++.h>
#define pb push_back
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
#define fastio() ios_base::sync_with_stdio(0),cin.tie(0)
using namespace std;
typedef long long ll;
const int MOD = 1e9+7;
const int INF = 0x3c3c3c3c;
const long long INFL = 0x3c3c3c3c3c3c3c3c;
 
struct node{
    int volt, id;
    bool operator<(const node& rhs) const{
        if(volt != rhs.volt) return volt < rhs.volt;
        return id < rhs.id;
    }
};
node socks[200003];
node coms[200003];
int N, M, a;
int C, U;
int A[200003], B[200003];
int checkS[200003], checkC[200003];
int main() {
    fastio();
    cin >> N >> M;
    for(int i = 0 ; i < N; i++) {
        cin >> a;
        coms[i] = node{a, i};
    }
    for(int i = 0 ; i < M; i++) {
        cin >> a;
        socks[i] = node{a, i};
    }
 
    sort(coms, coms + N);
    sort(socks, socks + M);
    for(int i = 0 ; i < 40; i++){
        int posS = 0, posC = 0;
        while(posC < N && posS < M){
            auto c = coms[posC];
            auto s = socks[posS];
            if(checkC[posC] || s.volt > c.volt) posC++;
            else if(checkS[posS] || s.volt < c.volt) posS++;
            else{
                C++;
                U += i;
                A[s.id] = i;
                B[c.id] = s.id + 1;
                checkS[posS] = checkC[posC] = 1;
                posC++;
                posS++;
            }
        }
        for(int j = 0 ; j < M; j++) socks[j] = node{(socks[j].volt + 1/ 2, socks[j].id};
    }
 
    cout << C << " " << U << "\n";
    for(int i = 0 ; i < M; i++cout << A[i] << " ";
    cout << "\n";
    for(int i = 0 ; i < N; i++cout << B[i] << " ";
    return 0;
}
cs


Comments