Codeforces Round #764 (Div. 3) 후기

A. Plus One on the Subset

풀이 보기

풀이

1번의 연산으로 배열의 특정 값들을 선택하여 값을 $1$ 증가시킬 수 있다. 이 때 배열의 모든 원소를 같게 만들기 위해 필요한 연산의 최솟값을 찾는 문제이다.

당연히, 최솟값을 최댓값으로 만들기 위해 필요한 연산의 수만큼 필요하지 않을까?

코드

#include <stdio.h>

#define min(a, b) (((a) > (b)) ? (b) : (a))
#define max(a, b) (((a) > (b)) ? (a) : (b))

int testcase;

int main() {
    scanf("%d", &testcase);

    for (int t = 1; t <= testcase; ++t) {
        int l;
        scanf("%d", &l);
        int minV = (int)(1e9 + 1), maxV = -1;
        for (int i = 0; i < l; ++i) {
            int a;
            scanf("%d", &a);
            minV = min(a, minV), maxV = max(a, maxV);
        }
        printf("%d\n", maxV - minV);
    }

    return 0;
}

B. Make AP

풀이 보기

풀이

세 수 $a,b,c$가 등차수열을 이루어야한다. 순서를 바꾸지 않아야한다는 조건이 문제를 좀 더 쉽게 한다.

세 수가 등차수열을 이루기 위한 조건은 $a+c=2\times b$이다. 여기서 우리는 최대 1번의 연산을 통해 등차수열을 만들 수 있는지 판단하면 된다. 숫자가 총 3개이므로 가능한 경우는 총 3개이다. 물론 연산을 안한다는 선택지도 있는데, 이건 곱하는 수 $m=1$인 경우라고 생각하자.

• $ma + c = 2b$
• $a + c = 2 mb$
• $a + mc = 2b$

즉, 위의 3가지 경우에 대해 식을 정리하고 $m = \cdots$ 형태로 바꾸면 된다. 이 때 $m$이 양의 정수로만 나오면 된다. 판단하는 방법은 나머지가 0인지 판별하는 과정이면 충분하다.

코드

#include <stdio.h>

int main() {

    int testcase;
    scanf("%d", &testcase);
    for (int t = 0; t < testcase; ++t) {
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);

        int temp = 2 * b - c;
        if (temp > 0 && temp % a == 0) {
            printf("YES\n");
            continue;
        } else {
            if ((a + c) % 2 == 0) {
                temp = (a + c) / 2;
                if (temp > 0 && temp % b == 0) {
                    printf("YES\n");
                    continue;
                }
            }
            temp = 2 * b - a;
            if (temp > 0 && temp % c == 0) {
                printf("YES\n");
                continue;
            }
        }
        printf("NO\n");
    }

    return 0;
}

C. Division by Two and Permutation

풀이 보기

풀이

풀이가 조금 이상하긴 한데 어쨌든 맞았죠? (나중에 더 간단하게 바꾸어야겠다..)

먼저 arr[]은 입력되는 배열, cnt[i]은 $i$의 개수를 의미한다. matrix[i][j]는 $i \rightarrow j$로 가는 방법이 있는지 없는지 알려주는 인접행렬이다.

문제 조건에 의해, arr[] 배열의 원소들을 순열로 바꿔야한다. 즉, 원소의 값들이 $1$부터 $n$까지 1개씩 존재해야한다. 그렇다면 입력된 배열의 원소들은 $n$보다 클 이유가 없다. 가능한 연산 또한 $2$로 나누는 과정밖에 없으므로, 입력 단계에서 미리 처리해두자.

그 다음 순열을 만들기 위한 과정을 거치도록 하자. 큰 수부터 처리하면 이후 연산들이 서로 간섭받지 않을 수 있을 것이다. 각 값들은 정확히 1개씩만 존재해야하므로, 존재하지 않다면 NO를 출력해버리면 된다. 만약 존재한다면 1개만 남기고 모두 연산을 수행하여 이후로 넘겨버리자.

모든 배열의 원소들이 문제의 조건에 맞게 된다면 YES를 출력하면 된다.

코드

#include <stdio.h>

typedef char bool;
const bool true = 1;
const bool false = 0;

#define MAX_IDX (50 + 1)
int arr[MAX_IDX];
int cnt[MAX_IDX];

bool matrix[MAX_IDX][MAX_IDX + 1];

void init() {
    for (int i = MAX_IDX - 1; i > 0; --i) {
        int temp = i;
        while (temp > 0) {
            matrix[i][temp] = true;
            temp >>= 1;
        }
    }
    return;
}

int main() {
    init();

    int testcase;
    scanf("%d", &testcase);
    for (int t = 0; t < testcase; ++t) {
        int n;
        scanf("%d", &n);
        for (int i = 0; i < MAX_IDX; ++i) {
            cnt[i] = 0;
        }
        for (int i = 0; i < n; ++i) {
            scanf("%d", arr + i);
            while (arr[i] > n) {
                arr[i] >>= 1;
            }
            ++cnt[arr[i]];
        }

        bool isProcessed = false;
        for (int i = n; i > 0; --i) {
            isProcessed = false;
            for (int j = MAX_IDX - 1; j > 0; --j) {
                if (matrix[j][i] == true && cnt[j] > 0) {
                    --cnt[j];
                    isProcessed = true;
                    break;
                }
            }
            if (!isProcessed) {
                printf("NO\n");
                break;
            }
        }

        if (isProcessed) {
            printf("YES\n");
        }
    }

    return 0;
}

결과

Contest	Start time	Rank	Solved	Rating change	New rating
#764 (Div. 3)	2022/1/10 23:35	3421	3	-9	1385