2021.01.03 PS - CEOI 2017 2번

CEOI 2017 Day 1 문제들

1번 문제       2번 문제      3번 문제

난이도 순서대로 2번 -> 1번 -> 3번 순서대로 풀 예정입니다.

 

2번. SURE BET

 

서브태스크 1 : N<=10 (20점)

 

고를지 말지 결정해야 할 베팅이 20개밖에 되지 않으므로, 모든 경우를 탐색해보면 지수 시간 안에 문제를 해결할 수 있습니다.

 

서브태스크 2 : N<=1000 (40점)

 

a 또는 b에서 몇 개를 고를 때는, 가장 큰 값들을 골라야 한다는 것은 자명합니다. 따라서 a와 b를 정렬해준 후, 총 m개를 고른다고 합시다. (0 <= m <- 2*n) 이 때 a에서 k개를 뽑고, b에서 m-k개를 뽑는 경우를 모든

max(0, m-n) <= k <= min(n, m)

에 대해서 골라준 후, 그 때의 이익을 계산하면 됩니다. 누적합을 미리 계산해놓으면 이익을 상수 시간 안에 구할 수 있어요. 정렬하는 데 시간복잡도가 O(n lg n), 계산하는데 시간복잡도가 O(n^2)이므로 최종 시간복잡도는 O(n^2)입니다.

 

 

소스 코드

#include <bits/stdc++.h>

using namespace std;

double a[1002];
double b[1002];

double sum_a[1002];
double sum_b[1002];

bool cmp(double x, double y){
    return x > y;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin >> n;
    for(int i=0;i<n;i++){
        cin >> a[i] >> b[i];
    }
    sort(a, a+n, cmp);
    sort(b, b+n, cmp);

    double ans = 0;

    sum_a[0] = 0, sum_b[0] = 0;
    for(int i=1;i<=n;i++){
        sum_a[i] = sum_a[i-1] + a[i-1];
        sum_b[i] = sum_b[i-1] + b[i-1];
    }

    for(int m = 1;m<=2*n;m++){
        for(int k=max(0, m-n);k<=min(m, n);k++){
            ans = max(ans, min(sum_a[k] - m, sum_b[m-k] - m));
        }
    }

    printf("%.4lf", ans);
}

 

서브태스크 3 : 추가 제한 없음 (40점)

 

N <= 100000이므로, 제곱 시간 미만으로 값을 찾아야 합니다. 서브태스크 2와 마찬가지로 큰 순서대로 정렬한 후 a에서 x개, b에서 y개를 골랐다고 할게요. 그리고 이때 a가 나올 경우 이익을 profit_a, b가 나올 경우 이익을 profit_b라고 할게요. 어느 하나를 더 선택했을 때 다른 하나의 이익은 감소하므로, profit_a와 profit_b 중 작은 값을 최대화하기 위해서는 더 작은 쪽의 하나를 골라야 합니다. 구체적인 증명은 생략합니다.

 

소스 코드

#include <bits/stdc++.h>

using namespace std;

double a[100002];
double b[100002];

bool cmp(double x, double y){
    return x > y;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin >> n;
    for(int i=1;i<=n;i++){
        cin >> a[i] >> b[i];
    }
    sort(a+1, a+n+1, cmp);
    sort(b+1, b+n+1, cmp);

    double profit_a = 0, profit_b = 0, ans = 0;

    for(int x = 0, y = 0; x + y < 2*n ;){
        if(x == n){
            y++;
            profit_a += -1;
            profit_b += b[y] - 1;
            ans = max(ans, min(profit_a, profit_b));
            continue;
        }
        if(y == n){
            x++;
            profit_a += a[x] - 1;
            profit_b += -1;
            ans = max(ans, min(profit_a, profit_b));
            continue;
        }

        if(profit_a > profit_b){
            y++;
            profit_a += -1;
            profit_b += b[y] - 1;
            ans = max(ans, min(profit_a, profit_b));
        }

        else{
            x++;
            profit_a += a[x] - 1;
            profit_b += -1;
            ans = max(ans, min(profit_a, profit_b));
        }
    }

    printf("%.4lf", ans);
}