Codeforces Round #712 (Div. 2)

Codeforces Round #712 (Div. 2)

 

Codeforces Round #712 (Div. 2)

 

Codeforces Round #712 (Div. 2)에 대한 해설입니다.

 

 * 이 글은 code-review 항목의 포스트입니다. code-review 항목에 대해 자세히 알아보고 싶다면, 클릭!

 * 문항 원문은 아래 주소에서 확인 가능합니다.

 

codeforces.com/contest/1504

Dashboard - Codeforces Round #712 (Div. 2) - Codeforces

 

[2021.04.04] 초판 발행 (A~D번)

 

 Codeforces Round #712 (Div. 2)에 대한 해설입니다. 이번 라운드의 주제는 déjà vu라는 말 답게, 어디서 많이 봤던 문제들이 많이 출제되었습니다. 특히, 전반적으로 좋은 아이디어를 생각해내면 풀이의 방향을 잡는 데에 도움이 되는 라운드였습니다. 개인적으로는 긴 슬럼프를 잠시 끝내는 라운드였습니다.

 

[A번] Déjà Vu (Codeforces 1504A)

 

[문제 및 풀이]

 

 이 문제는 영문자 a를 하나만 추가하였을 때, palindrome이 안 되게 하는 문자열을 만들 수 있는지, 만들 수 있다면 palindrome이 안 되는 문자열 하나를 출력하는 문제이다. 먼저, 해당 문자열을 만들 수 없는 경우는 주어진 문자열이 모두 a로 구성된 경우뿐이다. 그렇기 때문에 만들 수 없는 경우를 배제한다.

 

 Palindrome이 안 되는 문자열을 만드는 방법은 다양하다. 물론 한 군데씩 넣어보면서 답이 되는지 확인해도 $O(N^2)$의 시간복잡도를 가지지만, 답을 구하자마자 끝낸다면 주어진 시간 안에 정답을 구할 수 있다. 하지만 조금 더 보장이 되는 논리를 생각해보자. a를 주어진 문자열의 맨 앞에 넣거나, 맨 뒤에 넣는 방식이다. 일단 a를 맨 뒤에 넣은 다음에 palindrome이 되는지 확인하고, 만약 palindrome이면 a를 맨 앞에 넣으면 된다. 모든 문자열이 a가 아닌데도, 맨 앞에 a를 넣거나 맨 뒤에 a를 넣었을 때 모두 palindrome이 된다면 모순이기 때문에, 이 방법은 항상 가능함이 보장이 된다.

 

[예시 답안]

 

#include <stdio.h>
#include <string.h>
 
int N;
char in[350000];
 
void process() {
    int i;
 
    scanf("%s", in);
    N = strlen(in);
 
    for (i = 0; i < N; i++) if (in[i] - 'a') break;
 
    if (i == N) {
        printf("NO\n");
        return;
    }
 
    printf("YES\n");
 
    in[N] = 'a', in[N + 1] = 0;
 
    for (i = 0; i < N + 1; i++) if (in[i] - in[N - i]) break;
 
    if (i == N + 1) {
        in[N] = 0;
        printf("a%s\n", in);
    }
 
    else printf("%s\n", in);
}
 
int main() {
    int T;
 
    scanf("%d", &T);
    while (T--) process();
 
    return 0;
}
 

 

[B번] Flip the Bits (Codeforces 1504B)

 

[문제 및 풀이]

 

 $0$과 $1$로만 구성된 길이가 $n$인 문자열이 두 개 주어진다. 이 문자열에 대해서 다음 연산이 가능하다.

 

 "$1$번째 문자부터 $2k$번째 문자까지 $0$이 $k$개 나타나고 $1$이 $k$개 나타나는 경우, $1$번째 문자부터 $2k$번째 문자까지 각 문자를 $0$은 $1$로 $1$은 $0$으로 바꿀 수 있다."

 

 이 연산을 이용해서 한 문자열을 다른 문자열로 바꿀 수 있는지 확인하는 문제이다. 이 문제의 경우 먼저 풀이 방법을 설명하고, 그 풀이 방법이 왜 되는지 설명하는 방법으로 서술하고자 한다.

 

 먼저, $1 \leq i \leq n$에 대해서 $A[i]$와 $B[i]$와 같은 경우에는 $C[i]=0$이고, 다른 경우에는 $C[i]=1$이 되도록 하는 문자열 $C$를 만든다.

 

문자열 $C$를 만든 모습

 편의상, 문자열 $C$의 $0$은 흰색 부분으로 보고, $1$은 검은색 부분으로 보자. 그리고 같은 색이 연달아 있는 경우를 하나의 블록으로 묶어서 생각해보자. 제일 마지막에 나타나는 검정색 블록의 마지막 위치를 찾아놓자. 제일 마지막 블록이 흰색 블록이라면 어떤 문자열 구성이라도 상관이 없기 때문에 배제하는 것이다. (검정색 블록이 아예 안 나타나면 동일한 문자열이기 때문에 만들 수 있는 경우로 보면 된다.)

 

 첫번째 문자부터 검정색 블록의 마지막 위치까지 확인하면서 블록의 색이 바뀌는 위치가 나올 때마다, 그 위치까지 $1$과 $0$이 동일한 개수만큼 나타나는지 확인한다. 마지막 검정색 블록의 마지막 위치에서 이 확인하는 과정을 거치게 된다. 모든 확인 과정에서 $1$과 $0$이 동일한 개수가 나타난다면, 주어진 연산자를 통해서 한 문자열을 다른 문자열로 바꿀 수 있다.

 

 이 방법이 가능한 것은, 흰색 블록은 바꿀 필요가 없는 영역이고 검정색 블록은 바꿔야 하는 영역을 나타내기 때문이다. 다만, 흰색 블록이라도 그 뒤에 검정색 블록이 나타난다면, 그 위치를 다시 한 번 반전시켜야 할 필요가 있다. 그렇기 때문에 마지막 검정색 블록 이전의 모든 영역에서 주어진 연산을 한다는 것이 보장이 되어야 하고, 또 그렇게 보장이 되면 항상 도달하고자 하는 목적에 도달할 수 있기 때문에, 이런 확인하는 방법을 통해서 문제를 해결할 수 있다.

 

[예시 답안]

 

#include <stdio.h>
 
const int MAX = 350000;
 
int N, M;
int Cnt[MAX][2];
char A[MAX], B[MAX], C[MAX];
 
void process() {
    int i, c[2];
 
    scanf("%d%s%s", &N, A, B);
    for (i = c[0] = c[1] = 0; i < N; i++) c[A[i] - '0']++, Cnt[i][0] = c[0], Cnt[i][1] = c[1], C[i] = '0' + ((A[i] == B[i]) ? 0 : 1);
 
    for (i = N - 1; i >= 0; i--) if (C[i] == '1') break;
    M = i + 1;
 
    for (i = 1; i < M; i++) if (C[i - 1] - C[i] && Cnt[i - 1][0] - Cnt[i - 1][1]) break;
 
    if (M && Cnt[i - 1][0] - Cnt[i - 1][1]) i = -1;
 
    printf("%s\n", (i >= M) ? "YES" : "NO");
}
 
int main() {
    int T;
 
    scanf("%d", &T);
    while (T--) process();
 
    return 0;
}
 

 

[C번] Balance the Bits (Codeforces 1504C)

 

[문제 및 풀이]

 

 길이가 $n$인 두 개의 괄호 문자열 $A$와 $B$를 만드는 문제이다. 다만, $0$과 $1$로 구성된 길이가 $n$인 문자열 $S$가 주어진다. $S_i=1$이라면 $A_i = B_i$를 만족하고, $S_i=0$이라면 $A_i \neq B_i$를 만족해야 한다. 이 조건을 만족하는 문자열을 만들 수 없다면 만들 수 없음을 말하면 되고, 만들 수 있다면 만족하는 예시를 아무거나 하나 제시하면 된다. 이 문제 역시 먼저 풀이 방법을 설명하고, 그 풀이 방법이 왜 되는지 설명하는 방법으로 서술하고자 한다.

 

 일단 $S_1=1$이고 $S_n=1$을 만족하지 않으면 해당 조건을 만족하는 문자열을 만들 수 없다. (편의상, 문자열의 첫 문자는 $1$번째로 보고, 마지막 문자는 $n$번째로 본다.) 두 문자열 중 하나가 첫 문자가 $)$가 되거나, 마지막 문자가 $($ 되기 때문이다. 괄호 문자열은 두 문자가 쌍을 이루기 때문에, $1$과 $0$의 개수가 모두 짝수가 되어야 한다. ($n$이 짝수라는 것이 보장되기 때문에, 둘 중 하나가 짝수임이 보장되면 된다.) 이렇게 첫 글자와 마지막 글자가 $1$이고, $1$의 개수가 짝수라면 항상 가능(*1)하다.

 

 해당 조건을 만족하는 어떤 문자열을 하나 만드는 방법을 제시하면, 항상 가능함(*1)을 보일 수 있다. 일단 $S$에서 $1$인 것과 $0$인 것을 독립적인 것으로 보자. 그리고 $1$이 $2m$개 나타난다면, 처음 $m$개는 $($로 배치하고, 그 이후의 $m$가는 $)$를 배치한다. $0$이 $2k$개 나타난다면 홀수번째에 나타나는 것은 $($로 배치하고 짝수번째에 나타나는 것은 $)$로 배치하면 된다.

 

 이렇게 배치하면 항상 주어진 조건을 만족한다는 점을 확인하자. 괄호 문자열의 특성에 착안해서, $($는 $+1$에 대응하고, $)$는 $-1$에 대응하자. 괄호 문자열은 이렇게 대응한 수를 첫 문자부터 시작해서 합산을 해나가면서, 항상 음이 아닌 정수로 유지하면서, 마지막에는 $0$이 되어야 한다.

 

 첫 문자가 $($이고 마지막 문자가 $)$이기 때문에, $0$이 나타나는 위치에서는 항상 $1$ 이상임이 보장이 된다. 그렇기 때문에 중간에 $0$이 나타나는 위치에서 $)$이 나타나도 주어진 조건을 항상 만족한다. 또, $0$은 $($와 $)$가 번갈아 가면서 나타나기 때문에 $-1$, $+1$이나 $0$이 되는 효과만 주기 때문에 이 조건을 항상 만족한다. $1$의 경우에도 이 영역에서는 $1$부터 $m$까지 커졌다가, 다시 $1$으로 작아지는 효과를 준다. 그렇기 때문에, 이 방법을 이용하면 항상 주어진 조건을 만족하는 괄호 문자열을 만들 수 있고, 그렇기에 항상 가능함(*1)을 확인하였다. 이 방법은 직관적으로 이해하기 쉬운 한 가지 방법을 제안한 것일 뿐이기 때문에, 다른 방법으로 문제를 해결하는 방법을 배제한 것은 아니다.

 

[예시 답안]

 

#include <stdio.h>
 
const int MAX = 250000;
 
int N;
char in[MAX], A[MAX], B[MAX], c[5] = { "()" };
 
bool process() {
    int i, u, Cnt[2];
 
    scanf("%d%s", &N, in);
    if (in[0] == '0' || in[N - 1] == '0') return false;
 
    for (i = Cnt[0] = Cnt[1] = 0; i < N; i++) Cnt[in[i] - '0']++;
    if (Cnt[0] % 2 + Cnt[1] % 2) return false;
 
    for (i = u = 0; i < N; i++) if (in[i] == '1') A[i] = B[i] = c[u / (Cnt[1] / 2)], u++;
    for (i = u = 0; i < N; i++) if (in[i] == '0') A[i] = c[u], B[i] = c[u ^ 1], u ^= 1;
    A[N] = B[N] = 0;
 
    printf("YES\n%s\n%s\n", A, B);
 
    return true;
}
 
int main() {
    int T;
 
    scanf("%d", &T);
    while (T--) if (!process()) printf("NO\n");
 
    return 0;
}
 

 

 

[D번] 3-Coloring (Codeforces 1504D)

 

[문제 및 풀이]

 

 세 종류의 색($1$, $2$와 $3$)을 칠할 수 있는 $n \times n$ 크기의 놀이판을 두고, 두 사람이 게임을 하고 있다. 한 사람은 세 가지 종류의 색 중에 하나를 부르고, 나머지 한 사람은 놀이판의 어떤 위치에 그 사람이 말한 색을 제외한 색 중에 하나를 색칠해야 한다. 다만, 이 과정에서 인접한 두 칸 사이에 동일한 색이 칠해지면 안 된다. (색을 부르는 사람은 계속 색을 부르고, 색을 칠하는 사람은 계속 색을 칠한다.) 색을 칠하는 사람의 승리조건은 조건을 만족하면서 놀이판 전체를 색칠하는 것이고, 색을 칠하는 승리하지 못하면 색을 부르는 사람이 승리한다. 문제에서 구하는 것은 색을 칠하는 사람의 필승 전략을 구현하는 것이다. (문제에서 이런 필승 전략이 존재함은 보장된다고 나와 있다.)

 

 이 문제의 가장 큰 핵심은 동일한 색은 인접하지 않도록 칠하는 방법을 구상하는 것이다. 떠올리기 쉬운 한 가지 방법이 체스판과 같이 번갈아가면서 색칠하는 문제이다. 그래서 다음과 같은 전략을 생각할 수 있다. 놀이판의 특정 위치 $a_{i,j}$에 대해서, $i+j$가 짝수면 $1$을 칠하고, $i+j$가 홀수면 $2$를 색칠한다. 그림으로 그리면 다음과 같다.

 

놀이판에 1과 2를 배치한 모습

 

 만약 상대가 $3$을 부르면 위의 조건에 따라서 $1$과 $2$를 색칠하면 된다.  그리고 상대가 $1$을 부르면 $2$를, $2$를 부르면 부르면 $1$을 각각 색칠하면 된다. 그런데 $1$을 불렀는데 $2$를 색칠할 곳이 없다면 $1$을 색칠할 예정인 곳에 $3$을 색칠하면 되고, 마찬가지로 $2$를 불렀는데 $1$을 색칠할 곳이 없다면 $2$를 색칠할 예정인 곳에 $3$을 색칠하면 된다.

 

 이 방식으로하면 계속 $3$을 많이 불러도 $1$이나 $2$로 채우면 되고, $1$이나 $2$를 많이 부르면 그렇게 많이 부른 것을 $3$으로 대체할 수 있게 된다. 이런 식으로 대처를 하면 이 게임의 필승 전략을 제시했다고 볼 수 있다.

 

 (유의 사항) 인터렉티브(interactive) 유형의 공통된 사안이지만, 어떤 출력을 한 이후에 화면에 바로 출력이 되도록 하는 명령어를 넣어야 한다. C언어로 구현하는 경우에는 출력을 한 이후에 fflush(stdout)를 반드시 넣어야 한다.

 

[예시 답안]

 

#include <stdio.h>
 
int N, M;
int m[150][150];
int dir[4][2] = { 1,0,0,1,-1,0,0,-1 };
 
bool check(int y, int x) {
    int i, ny, nx;
 
    for (i = 0; i < 4; i++) {
        ny = y + dir[i][0], nx = x + dir[i][1];
        if (ny < 0 || nx < 0 || ny >= N || nx >= N) continue;
        if (m[ny][nx] == 3) return false;
    }
 
    return true;
}
 
void turn() {
    int i, u;
 
    scanf("%d", &M);
 
    if (M == 3) {
        for (i = 0; i < N; i++) {
            for (u = 0; u < N; u++) if (!m[i][u]) break;
            if (u < N) break;
        }
 
        m[i][u] = (i + u) % 2 + 1;
        printf("%d %d %d\n", (i + u) % 2 + 1, i + 1, u + 1);
    }
 
    else{
        for (i = 0; i < N; i++) {
            for (u = 0; u < N; u++) if (!m[i][u] && ((i+u)%2+1)!=M) break;
            if (u < N) break;
        }
 
        if (i<N){
            m[i][u] = (i + u) % 2 + 1;
            printf("%d %d %d\n", (i + u) % 2 + 1, i + 1, u + 1);
        }
 
        else {
            for (i = 0; i < N; i++) {
                for (u = 0; u < N; u++) if (!m[i][u] && check(i,u)) break;
                if (u < N) break;
            }
 
            m[i][u] = 3;
            printf("%d %d %d\n", 3, i + 1, u + 1);
        }
    }
 
    fflush(stdout);
}
 
int main() {
    int i;
 
    scanf("%d", &N);
    for (i = 0; i < N*N; i++) turn();
 
    return 0;
}
 

 

[E번] (작성 전) (Codeforces 1504E)

 

[문제 및 풀이]

 

 

 

[예시 답안]

 

 

 

[F번] (작성 전) (Codeforces 1504F)

 

[문제 및 풀이]

 

 

 

[예시 답안]