Codeforces Round #742 (Div. 2) 후기

A. Domino Disaster

풀이 보기

풀이

사용할 수 있는 도미노는 총 4종류. 덮어야하는 줄은 2줄이다. 여기서 Alice가 위 또는 아래 1줄의 정보를 알려준다. 우리는 이 정보를 토대로 다른 줄의 도미노를 알아내야한다.

잠깐 고민해보면 알겠지만, 입력되는 문자에 대해 일대일 대응이 성립한다는 것을 알 수 있다. U라면 D, D라면 U. 세로 도미노가 아니라면 가로 도미노라는 얘기이며, 이 때에는 LR로 출력하면 된다.

코드

#include <stdio.h>

#define M 100 + 1

char str[M];
char ret[M];
int n;

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        scanf("%d", &n);
        scanf("%s", str);

        int i;
        for (i = 0; str[i]; ++i) {
            if (str[i] == 'U') {
                ret[i] = 'D';
            } else if (str[i] == 'D') {
                ret[i] = 'U';
            } else {
                ret[i] = 'L', ret[++i] = 'R';
            }
        }
        ret[i] = '\0';
        printf("%s\n", ret);
    }
    return 0;
}

B. MEXor Mixup

풀이 보기

풀이

배열의 최종 $MEX$와 $XOR$이 주어졌을 때, 만들 수 있는 배열의 최소 길이를 출력하라는 문제이다.

우선 우리는 $MEX$를 통해 $0$부터 $MEX-1$까지는 배열에 들어있어야 하며, $MEX$는 배열에 존재하지 않음을 알 수 있다. 그럼 우선 $0$부터 $MEX-1$까지는 미리 ^ 연산을 해두어 값을 $x$에 저장하자.

이제 이 $x$값과 $XOR$값을 토대로 최종 배열의 길이를 유추해낼 수 있다.

• $x = XOR$인 경우 : 배열이 이미 만들어졌으므로 현재 길이를 출력한다
• $x~\oplus~MEX = XOR$인 경우 : 값을 1개만 추가한다고 만들 수 있는 상황이 아니다. 현재 길이에 $2$를 더해 출력한다
• 이외의 경우 : $x~\oplus~XOR$ 하나만 넣어주면 원하는 배열을 얻어낼 수 있다. 현재 길이에 $1$을 더해 출력한다

코드

#include <stdio.h>

#define M 300010

int arr[M];

int main() {
    for (int i = 1; i < M; ++i) {
        arr[i] = arr[i - 1] ^ i;
    }

    int t;
    scanf("%d", &t);
    while (t--) {
        int a, b;
        scanf("%d %d", &a, &b);
        int x = arr[a - 1];

        if (x == b) {
            printf("%d\n", a);
        } else if ((x ^ a) == b) {
            printf("%d\n", a + 2);
        } else {
            printf("%d\n", a + 1);
        }
    }
    return 0;
}

결과

Contest	Start time	Rank	Solved	Rating change	New rating
#742 (Div. 2)	2021/9/5 23:35	2954	2	+28	1394