Good Bye, BOJ 2021!

오늘 대회가 있는 줄 몰랐는데, 마침 백준 들어갔더니 보이길래 참가했다. 상품은 받을 실력이 안 되는 것을 알기 때문에, 그냥 solved.ac 배경이랑 뱃지 받으려고 참가했다.

정말 오랜만에 PS를 해보는 것이라 괜히 긴장이 되었다.

결과적으로는 A, B, C를 풀었다. D부터는 대회시간 안에 못 풀것 같아서 그냥 쨌다.

A번은 바로 풀었는데, 에라토스테네스의 체를 이용해서 소수를 구한뒤, 주어진 $n$보다 클때까지 그냥 연속적인 소수를 곱하는 방법이다.

#include <cstdio>
#include <vector>
#define MAX 1000000
int prime[MAX], n;
std::vector<int> primes;

int main() {
    scanf("%d", &n);
    for(int i = 2; i < MAX; i++) prime[i] = true;
    for(int i = 2; i*i< MAX; i++) {
        if(!prime[i]) continue;
        primes.push_back(i);
        for(int j = i*i; j < MAX; j += i) {
            prime[j] = false;
        }
    }
    //for(auto i:primes) printf("%d ", i);
    for(int i = 0; i < primes.size() -1; i++) {
        if(primes[i]*primes[i+1] > n) {
            printf("%d\n", primes[i]*primes[i+1]);
            break;
        }
    }
    return 0;
}

B번은 생각하는데 10분정도 시간이 걸렸다.

예쁜 케이크의 조건은 다음과 같은데, 

1. 케이크는 높이가 $1$이고, 부피가 $N$인 직육면체 모양이다.
2. 케이크를 적절히 칼질해서 한 변의 길이가 $1$인 정육면체 모양 조각 $N$ 개로 나눌 수 있어야 한다.
3. 케이크의 옆면에 가로 너비가 $1$인 직사각형을 이어 붙여 만든 띠를 딱 맞게 두를 수 있어야 한다.
4. 장식용 띠는 가로 폭이 $1$인 빨간색, 초록색, 하얀색 직사각형이 순서대로 번갈아 가면서 같은 개수만큼 나와야 한다.

여기서 조건 2에 의해, $N = ab$와 같이 분해되어야 함을 알 수 있고, 조건 4에서 $2a + 2b$가 3으로 나누어 떨어져야 함을 알 수 있다. 즉, $a+b$가 3으로 나누어 떨어져야 하고, 이는 $\{(a\%3) + (b\%3)\}\%3 = 0$이라는 것이므로, 

$a = 3n, b = 3m$ 또는 $a = 3n +1, b =3m +2$인 경우가 가능함을 알 수 있다.

이에 $N = ab$를 구해보면, $N = 9nm$ 또는 $N = 9nm + 3m + 6n + 2$임을 알 수 있다. 즉, $N \% 9 = 0$이거나, $N \%3 = 2$이면 예쁜 케이크를 만들 수 있고, 그렇지 않으면 예쁜 케이크를 만들지 못함을 알 수 있다. 

 

처음에는 $n % 3 \neq 1$이기만 하면 된다고 생각해서 틀렸고, 그다음엔 long long을 입력받을때 scanf("%d", ~)로 받아서 3번 틀리고 맞았다.

#include <cstdio>

int T;
long long n;

int main() {
    scanf("%d", &T);
    while(T--) {
        scanf("%lld", &n);
        if(n % 9 == 0 ||n % 3 == 2) {
            printf("TAK\n");
        }
        else {
            printf("NIE\n");
        }
    }
    return 0;
}

C번은 중간에 가족이랑 아이스크림을 40분 정도 먹다가, 생각나서 한 20분정도 코딩하고 40분동안 뇌절했다.

나는 파라메트릭 서치로 풀었다. 만약 $t$일에 밀키트를 먹을 수 없다면, $t+n(n \geq 0)$일에도 밀키트를 먹을 수 없을 것이다. 또한, $t$일에 밀키트를 먹을 수 있는지 판단하는 것은 쉽다. 직접 $S_i \times \text{max}(1, t-L_i)$를 계산한뒤, 정렬하고 $O_i = 1$인 것들 중 $S_i \times \text{max}(1, t-L_i)$가 큰 순서대로 $k$개 제외하고 구한 합이 $G$보다 작은지 판단하면 된다. 시간복잡도는 $\mathcal{O}(N\log T + N\log N \log T)$($T$는 상수긴 한데, 빼고 쓰기도 뭐한 것 같아서 같이 써줬다. 이럴때 어떻게 써줘야할지 헷갈린다..)이다. 여기서 $T = 2\times 10^9$인데, 이유는

입력이
1 1000000000 0

1 1000000000 0

로 주어졌을때 가장 오랫동안 먹을 수 있음이 자명하고, 이경우 $2 \times 10^9$일 뒤까지 먹을 수 있기 때문이다.

그리고 이는 이분탐색을 할때 상한선이 되어주기도 한다.

 

자료형때문에 40분동안 뇌절했고, 8번 틀렸다. tmp 배열의 값을 계산하면서 문제가 생길 수 있다는 것까진 예상을 했어서 빨리 고쳤는데, max함수를 int max(int a, int b)로 선언해서 계속 틀렸다. 

#include <cstdio>
#include <algorithm>
int n, g, k, s[200'010], l[200'010], o[200'010], cnt;
std::pair<unsigned long long, int> tmp[200'010];
unsigned long long sum;

long long max(long long a, long long b) {
    return (a>b)?a:b;
}

int calc(unsigned long long t) {
    for(int i = 0; i < n; i++) {
        tmp[i].first = s[i]*max(1, t -l[i]);
        tmp[i].second = i;
    }
    std::sort(tmp, tmp+n);
    cnt = 0;
    sum = 0;
    for(int i = n-1; i >= 0; i--) {
        if(o[tmp[i].second] && cnt < k) {
            cnt++;
            continue;
        }
        sum += tmp[i].first;
        if(tmp[i].first > g || sum > g) return false;
    }
    //printf("%lld\n", sum);
    return true;
}

int main() {
    scanf("%d %d %d", &n, &g, &k);
    for(int i = 0; i < n; i++) {
        scanf("%d %d %d", &s[i], &l[i], &o[i]);
    }
    unsigned long long s = 0;
    unsigned long long mid;
    unsigned long long e =2e9+4;
    while(s +1 < e) {
        mid = (s+e)/2;
        if(calc(mid)) {
            s = mid;
        }
        else {
            e = mid;
        }
    }
    printf("%lld\n", s);
    return 0;
}

오랜만에 PS를 했는데도 오히려 옛날보다 실력이 늘어난 것 같다. 여전히 미천하긴 하지만.. 이제 방학이니 학교공부와 PS둘다 열심히 해야겠다.