Codeforces Round #734 (Div. 3) 후기

A. Polycarp and Coins

풀이 보기

풀이

문제를 한줄로 설명하면, 두 묶음 $c_1$과 $c_2$이 있을 때, 정확히 $c_1 + 2 \times c_2 = n$이 나오도록 하면서도 $\min \vert c_1 - c_2 \vert$를 구하는 문제가 되겠다.

결론을 바로 얘기하자면, 항상 차이를 1 이하로 만들 수 있다. 각 묶음이 $1$과 $2$를 대표하고 있기에 가능한 일. 두 묶음을 같은 갯수만큼 사용하면 $3$을 대표하는 묶음을 사용하는 것과 같은 의미로 생각할 수 있다. 그럼 $n$을 $3$으로 나눈 몫 $q$만큼은 $c_1$과 $c_2$가 사용할 수 있다. 이후 나머지 $r \in \lbrace 0, 1, 2 \rbrace$ 중에서 하나 나올 것이다. 이후 나머지의 값에 따라 아래와 같이 진행하면 된다.

• $r = 0$인 경우 : $n = 3 \times q = 1 \times q + 2 \times q$이므로, $c_1 = c_2 = q$로 나타낼 수 있다
• $r=1$인 경우 : $n = 3 \times q + 1 = 1 \times (q+1) + 2 \times q$이므로, $c_1 = q + 1, c_2 = q$로 나타낼 수 있다
• $r=2$인 경우 : $n = 3 \times q + 2 = 1 \times q + 2 \times (q+1)$이므로, $c_1 = q, c_2 = q + 1$로 나타낼 수 있다

코드

#include <stdio.h>
 
int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        int n;
        scanf("%d", &n);
        int a = n / 3 + (n % 3 == 1), b = n / 3 + (n % 3 == 2);
        printf("%d %d\n", a, b);
    }
    return 0;
}

B1. Wonderful Coloring - 1

풀이 보기

풀이

조건 2에 의해, 특정 문자 $c$는 최대 2개까지만 고려하면 된다. 같은 문자는 같은 색깔을 칠할 수 없고, 색깔은 빨강과 초록밖에 없기 때문이다. 나머지는 모두 흰색이라는 것. 문제에서는 색깔이 칠해진 문자들만 세려고 하므로, 문자 $c$가 아무리 많아도 우리는 2개까지만 생각하면 된다. 그럼 모든 문자들의 존재 개수가 $\lbrace 0, 1, 2 \rbrace$ 안에 존재하게 된다. 이 때 아래와 같은 고민을 해보자.

• 문자 $c$가 $0$개 존재하는 경우 : 고려할 필요가 없다
• 문자 $c$가 $2$개 존재하는 경우 : 하나씩 빨강과 초록으로 색칠하자
• 문자 $c$가 $1$개 존재하는 경우 : 다른 문자 $d$와 하나의 쌍으로 생각하자. $c$를 빨강, $d$를 초록으로 칠하면 된다

모든 문자에 대해 이렇게 고려해보면, 정답 $2k = \sum_a^z \min(cnt, 2)$라는 것을 알 수 있다. 우리가 원하는건 $k$이므로 $2$로 나누어주자.

코드

#include <stdio.h>
 
char str[51];
int alpha[26];
 
int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        for (int i = 0; i < 26; ++i) {
            alpha[i] = 0;
        }
 
        scanf("%s", str);
        int len;
        for (len = 0; str[len]; ++len) {
            ++alpha[str[len] - 'a'];
        }
 
        for (int i = 0; i < 26; ++i) {
            if (alpha[i] > 2) {
                len -= (alpha[i] - 2);
            }
        }
        //printf("t : %d\n", len);
 
        printf("%d\n", len >> 1);
    }
    return 0;
}

결과

Contest	Start time	Rank	Solved	Rating change	New rating
#734 (Div. 3)	2021/7/23 23:35		2		1628

Expert는 Div. 3에서 unrate라고 한다. 친구들 참여하는거 옆에서 불구경한게 되어버렸다.

모두 사이좋게 2문제 풀었다. performance가 1300점보다 밑인 것 같다. 이거 rate되어버렸으면 큰일날뻔..