Codeforces Round #634 (Div. 3) 후기

A. Candies and Two Sisters

풀이 보기

풀이

$n$개의 캔디가 주어지고 그것을 2명이 나누어 가질 때, $a$가 $b$보다 큰 경우의 수를 구하는 문제이다. 기본적으로 $\frac{1}{2}\times n$가지의 경우의 수가 있다.

$0$개를 주는 경우의 수는 없어야하므로, $n$이 홀수인 경우에는 추가로 1가지의 경우를 더 빼주어야 한다.

코드

#include <stdio.h>

int main(t) {
    for (scanf("%d", &t); t; t--) {
        long long n;
        scanf("%lld", &n);
        if (n < 3) {
            printf("0\n");
        }
        else {
            int temp = (n % 2);
            n /= 2;
            n -= (!temp);
            printf("%lld\n", n);
        }
    }
    return 0;
}

B. Construct the String

풀이 보기

풀이

정답 문자열의 모든 $a$ 길이의 substring들은 모두 정확히 $b$개의 문자만으로 이루어지도록 구현하는 문제이다. 규칙이 어렵다고 느낄 수 있지만, 그저 “abcabcabc”와 같이 $b$개의 문자가 반복되도록 문자열을 정하면 모든 경우에서 정답을 출력할 수 있는 간단한 문제이다.

코드

#include <stdio.h>

int main(t) {
    for (scanf("%d", &t); t; t--) {
        int n, a, b;
        scanf("%d %d %d", &n, &a, &b);
        for (int i = 0; i < n; i++)
            printf("%c", i % b + 'a');
        printf("\n");
    }
    return 0;
}

C. Two Teams Composing

풀이 보기

풀이

주어진 학생들의 skill level에 대하여 2개의 팀으로 나누는 작업에서, 아래의 조건을 만족하면서 가장 많은 학생을 팀으로 만들 수 있는 경우를 찾는 문제이다.

• 1팀에 속한 모든 학생의 skill level은 달라야 한다.
• 2팀에 속한 모든 학생의 skill level은 같아야 한다.

먼저 1번 팀을 만들 때 가장 많은 학생 수를 $a$로 기록한다. 그리고 2번 팀을 만들 때 가장 많은 학생 수를 $b$로 기록한다. 이 2개의 숫자를 이용하여 최적으로 2개의 팀을 만드는 경우를 탐색한다.

기준은 b의 값을 이용하여 최대를 판별한다. 풀이에서는 총 3가지의 경우를 고려하였다.

• $a≥b+1$인 경우
  • 2팀을 $b$명의 학생으로 모두 묶더라도 1팀의 인원을 충족시킬 인원이 있다. 따라서 팀을 꾸릴 수 있는 최대 인원은 $b$명이다.
• $a=b$인 경우
  • 2팀을 $b$명의 학생으로 묶는다면 1팀의 인원이 1명 부족하다. 따라서 팀을 꾸릴 수 있는 최대 인원은 $b-1$명이다.
• 그 이외의 경우
  • 1팀의 인원을 최대로 하더라도 2팀의 인원을 충족시킬 인원이 있다. 따라서 팀을 꾸릴 수 있는 최대 인원은 $a$명이다.

코드

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

cmp(int *a, int* b) {
    return *a - *b;
}

main(t) {
    for (scanf("%d", &t); t; t--) {
        int arr[200000];
        int n;
        scanf("%d", &n);
        for (int i = 0; i < n; i++)
            scanf("%d", arr + i);
        qsort(arr, n, sizeof(int), cmp);
        if (n == 1) {
            printf("0\n");
            continue;
        }
        int m = 0, temp = 1, count = 1;
        for (int i = 1; i < n; i++)
            if (arr[i] != arr[i - 1])
                m = max(m, temp), temp = 1, count++;
            else
                temp++;
        m = max(m, temp);
        int a = m, b = count;

        if (a >= b + 1)
            printf("%d\n", b);
        else if (a == b)
            printf("%d\n", b - 1);
        else
            printf("%d\n", a);
    }
    return 0;
}

D. Anti-Sudoku

풀이 보기

풀이

최대 9칸을 변경할 수 있다는 조건이 있고, 각 가로줄 또는 세로줄에 공통된 값이 존재해야한다는 조건이 있다. 이를 통해 각각의 줄에서 값을 하나씩만 바꾸는 것으로 anti-sudoku를 만들 수 있다. 그리고 값이 변경되는 위치는 가로 또는 세로에서 각각 겹치지 않아야 한다. 또한 3x3 크기의 정사각형 구역에서도 겹치는 위치가 없어야 한다.

변경되는 값들은 기존 값에서 $1$만큼 증가시켜 이미 있던 수들 중 하나와 같은 값을 가지도록 조절한다. 기본적으로 입력으로 sudoku가 완성되어 주어지므로 가능한 추론이다.

코드

#include <stdio.h>

int pos[9] = {
    0, 3, 6,
    1, 4, 7,
    2, 5, 8 };

int main(t) {
    for (scanf("%d", &t); t; t--) {
        char str[9][10];
        for (int i = 0; i < 9; i++) {
            scanf("%s", str[i]);
            str[i][pos[i]]++;
            str[i][pos[i]] -= 9 * (str[i][pos[i]] > '9');
        }
        for (int i = 0; i < 9; i++)
            printf("%s\n", str[i]);
    }
    return 0;
}

결과

Contest	Start time	Rank	Solved	Rating change	New rating
#634 (Div. 3)	2020/4/13 23:35	16046	1	-132	1368

Codeforces 첫 참여였다. 컨테스트 시간을 몰랐어서 상당한 시간이 지난 뒤부터 참여하게 되어버렸다. (2시간동안 진행되는데, 끝나기 30분 전부터 시작했다..) 위의 해설에는 총 4문제가 설명되어있지만, 실제 컨테스트 기간에는 A번 문제밖에 풀지 못했다.

시간이 촉박하다고 작성한 코드를 제대로 확인하지 않고 무작정 제출한 경우가 많았고, 대부분 컴파일 에러를 받았다. contest 중에는 시간에 쫓기지 않고 자신의 페이스를 유지하는 습관을 길러야겠다.