Codeforces Round 595 (Div. 3) 후기 및 문제 풀이

후기

9문제 중 5문제 풀었는데도 1600등이라니ㅎㅎ

확실히 Div 2 보다 문제의 난이도가 괜찮았지만 여전히 Hard version은 어려웠다.

풀이는 Editorial을 참고해서 만들었다.

A. Yet Another Dividing into Teams

더 간단한 방법이 있을 것 같으나, q와 n의 사이즈를 확인한 후에 바로 직관적으로 풀어보려고 했다.

팀의 가장 최근에 들어간 학생의 값을 담고 있는 어레이를 하나 준비한다.

학생을 다 sort 한 후에 처음부터 빈 팀이나 들어갈 수 있는 팀을 찾아 넣는다.

모든 학생을 다 넣으면 비지 않은 팀의 개수를 출력한다.

#include <cstdio>
#include <algorithm>
using namespace std;
int q, n, arr[101];
int main(){
    scanf("%d", &q);
    while(q--){
        scanf("%d", &n);
        int team[101] = {0,};
        for(int i = 0 ; i < n; i++)scanf("%d", &arr[i]);
        sort(arr, arr + n);
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                if(!team[j] || arr[i] - team[j] != 1){
                    team[j] = arr[i];
                    break;
                }
            }
        }
        for(int i = 0; i <= n; i++){
            if(team[i] == 0){
                printf("%d\n", i);
                break;
            }
        }
    }
}

B. Books Exchange

문제 링크(Easy)

문제 링크(Hard)

이 문제의 easy 버전에는 그냥 하나 하나 일일이 확인해주는 방법을 이용해서 결과를 확인했다.

근데 하나의 책이 제자리에 돌아오는 길에 있는 모든 학생은 같은 값을 가지게 된다는 걸 알게 됐다.

나는 par라는 어레이를 두어서 a의 책이 도는 과정에 있는 모든 학생의 par를 a로 만들어주어 연산을 줄였다.

#include <cstdio>
int q, n, p[200001], par[200001], v[200001];

int main(){
    scanf("%d", &q);
    while(q--){
        scanf("%d", &n);
        for(int i = 1; i <= n; i++){
            scanf("%d", &p[i]);
            par[i] = i;
        }
        for(int i = 1; i <= n; i++){
            if(par[i] != i){
                v[i] = v[par[i]];
                continue;
            }
            int temp = i, cnt = 1;
            while(p[temp] != i)temp = p[temp], cnt++, par[temp] = i;
            v[i] = cnt;
        }
        for(int i = 1; i <= n; i++)printf("%d ", v[i]);
        
        printf("\n");
    }
}

C. Good Numbers

문제 링크(Easy)

문제 링크(Hard)

easy 버전은 n이 최대 10000이기 때문에 어레이에 3의 제곱으로 만들 수 있는 수의 위치에 1을 표시했다.

hard 버전은 n이 10의 18 승이기 때문에 어레이 사용이 불가능하다.(이 문제는 다른 풀이를 참고했다.)

먼저 n을 받은 후에 이를 3진수로 표현한다고 하면 1과 2로 표현이 가능할 것이다. 3은 $10_3$, 5는 $12_3$ 이렇게 말이다.

이 때 2가 없다면 n이 정답이다. 그렇지 않은 경우에는 다음을 진행한다.

$pos_2$를 왼쪽에서 제일 먼저 있는 2의 위치라 하고 $pos_0$을 $pos_2$ 의 왼쪽에 있는 최초 0의 위치라고 하자.

이 때 $3^(pos_0)$을 n에 더해주고 $pos_0$의 오른쪽부터 0까지의 값을 다 0으로 만들어주면 정답이다.

예를 들어, 14 같은 경우에는 3진수로 표현하면 $112_3$인데 2를 없애기 위해서 2의 왼쪽 최초 0을 1로 바꾸고 그 오른쪽을 다 0으로 만든 $1000_3$이 답이 된다.

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
long long n, temp, q, three[50], n1;
int main(){
    //3으로 만들 수 있는 총 가지수를 만들어
    for(long long i = 1; i < 1350851717672992090; i *= 3)three[n1++] = i;
    scanf("%lld", &q);
    while(q--){
        scanf("%lld", &n);
        int arr[50] = {0,}, n2 = 0, pos2 = -1, pos0 = -1;
        temp = n;
        //3진수 만들기
        while(temp)arr[n2++] = temp % 3, temp /= 3;
        //pos2 찾기
        for(int i = n2 - 1; i >= 0; i--){
            if(arr[i] == 2){
                pos2 = i;
                break;
            }
        }
        //이미 good이면 출력
        if(pos2 == -1){
            printf("%lld\n", n);
            continue;
        }
        //pos0 찾기
        for(int i = pos2 + 1; i < 50; i++){
            if(arr[i] == 0){
                pos0 = i, n += three[pos0];
                break;
            }
        }
        //pos0 아래 값들 다 빼주기
        for(int i = 0; i < pos0; i++)n -= three[i] * arr[i];
        printf("%lld\n", n);
    }
}

D. Too Many Segments

이 문제는 그리디로 접근할 수 있다.

cover된 정도를 다 기록해두고 0부터 값이 k를 초과하는 위치에 해당하는 원소로 부터 뒤가 제일 긴 애를 제거해서 해당 위치 값이 k를 넘지 않게 한다.

prefix sum을 이용하면 시간적인 측면을 훨씬 개선 할 수 있다.

E. By Elevator or Stairs?

이 문제는 대회 때 직접 풀었다!

제한 사항을 봤을 때, 2십만의 경우의 수를 2초안에 구하면 약 1000번 정도의 연산을 해야한다.

이것은 n*n으로는 풀 수 없기 때문에 n번이나 nlogn번으로 끝낼 수 있는 방법이 필요했다.

나는 각 층(i)을 갈 수 있는 경우의 수를 2개로 나눠서 접근했다.

(i-1: 엘베, i: 엘베)와 (i-1: 계단, i: 엘베) 중 작은 값을 엘베 값으로 저장하고

(i-1: 엘베, i: 계단)와 (i-1: 계단, i: 계단) 중 작은 값을 계단 값으로 저장했다.

이렇게 디피를 이용해서 풀어나가면 n번만에 연산을 끝낼 수 있었다.

#include <cstdio>
#include <algorithm>
using namespace std;
int n, c, temp, a[200002], b[200002], ans[200001][2];
int main(){
    scanf("%d %d", &n, &c);
    for(int i = 1; i < n; i++)scanf("%d", &a[i]);
    for(int i = 1; i < n; i++)scanf("%d", &b[i]);
    ans[0][0] = c;
    for(int i = 1; i < n; i++){
        ans[i][0] = min(ans[i-1][0] + b[i], ans[i-1][1] + b[i] + c);
        ans[i][1] = min(ans[i-1][0] + a[i], ans[i-1][1] + a[i]);
    }
    for(int i = 0; i < n; i++)printf("%d ", min(ans[i][0], ans[i][1]));
}

느낀점

코드포스를 풀기 시작하면서 수학의 필요성을 절실히 느낀다.

조금씩이라도 접근법을 경험해보면서 수학 능력도 길러지길 바래본다.