Codeforces Round #738 (Div. 2) 후기

A. Mocha and Math

풀이 보기

풀이

배열의 특정 구간을 잡고, 그 구간에서 & 연산이 무한히 가능할 때, 배열의 최댓값을 최소화하고 싶다는 문제이다. 아래 특징만 알고 있다면 쉽게 풀 수 있다.

• 같은 구간을 선택하는건 의미없다. 연산을 여러번 진행한다고 값이 바뀌지는 않는다
• $a \& b$ 연산은 그 값이 커지지 않는다

결론으로는, 모든 구간에 대해 & 연산을 수행해버리면 정답을 얻을 수 있다.

코드

#include <stdio.h>
 
typedef long long ll;
 
int n;
 
int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        int n;
        ll ret;
        scanf("%d %lld", &n, &ret);
        for (int i = 1; i < n; ++i) {
            ll a;
            scanf("%lld", &a);
            ret &= a;
        }
        printf("%lld\n", ret);
    }
    return 0;
}

B. Mocha and Red and Blue

풀이 보기

풀이

완벽한 경우는 “배열이 R과 B가 반복되는 구조”이며, 인접한 두 큐브가 같은 색이라면 불완벽성이 $1$ 증가한다.

처음 나오는 R 또는 B에 따라 그 위치에서 두 색깔이 교차되게, 그리디하게 배치하면 된다.

코드

#include <stdio.h>
 
typedef long long ll;
 
#define M 101
 
char str[M];
int n;
 
int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        scanf("%d", &n);
        scanf("%s", str);
 
        int i = 0;
        while (str[i] == '?') {
            ++i;
        }
        if (i == n) {
            for (i = 0; i < n; ++i) {
                str[i] = ((i & 1) ? 'B' : 'R');
            }
        } else {
            if (str[i] == 'R') {
                for (int j = i - 1; j >= 0; --j) {
                    str[j] = (((i - j) & 1) ? 'B' : 'R');
                }
            } else {
                for (int j = i - 1; j >= 0; --j) {
                    str[j] = (((i - j) & 1) ? 'R' : 'B');
                }
            }
        }
 
        for (; i < n; ++i) {
            if (str[i] == '?') {
                str[i] = ((str[i - 1] == 'R') ? 'B' : 'R');
            }
        }
        printf("%s\n", str);
    }
    return 0;
}

C. Mocha and Hiking

풀이 보기

풀이

Not solved

result : Wrong answer on test 57

 생애 첫 해킹당했다!

코드

D. Mocha and Diana (Easy Version)

풀이 보기

풀이

사이클이 생기지 않는 선에서, 같은 간선을 추가하여 두 forest가 계속 유지될 수 있도록 하는 문제다.

이미 다른 방법으로 연결된 두 정점들은 간선을 추가하면 사이클이 생겨버린다. 즉 서로 연결되어있지 않은 정점들에 대해서만 간선을 추가해나가면 된다. 여기서 사용할 수 있는 방법이 유니온파인드가 되겠다. 간선이 연결되면 그 정점들을 같은 set에 넣을 수 있다. 이렇게 하면 하나의 set에 존재한다면 그 정점들을 잇는 간선을 연결할 수는 없다는 것을 의미한다. 두 forest에 대해서, 두 정점을 골랐을 때 두 정점이 모두 서로 다른 set에 존재하는 경우에만 간선을 추가해나가면 된다.

코드

#include <stdio.h>

typedef struct Node {
    int x, y;
} ND;
#define M 1001

int parent1[M], parent2[M];
int n, m1, m2;
ND result[M];
int len;

int find1(int x) {
    if (x == parent1[x]) {
        return x;
    } else {
        return parent1[x] = find1(parent1[x]);
    }
}
int find2(int x) {
    if (x == parent2[x]) {
        return x;
    } else {
        return parent2[x] = find2(parent2[x]);
    }
}

void merge1(int a, int b) {
    int x1 = find1(a), y1 = find1(b);

    if (x1 > y1) {
        parent1[x1] = parent1[a] = y1;
    } else {
        parent1[y1] = parent1[b] = x1;
    }
    return;
}
void merge2(int a, int b) {
    int x2 = find2(a), y2 = find2(b);

    if (x2 > y2) {
        parent2[x2] = parent2[a] = y2;
    } else {
        parent2[y2] = parent2[b] = x2;
    }
    return;
}

void merge(int a, int b) {
    merge1(a, b);
    merge2(a, b);
    return;
}

int main() {
    scanf("%d %d %d", &n, &m1, &m2);
    for (int i = 1; i <= n; ++i) {
        parent1[i] = parent2[i] = i;
    }
    while (m1--) {
        int a, b;
        scanf("%d %d", &a, &b);
        merge1(a, b);
    }
    while (m2--) {
        int a, b;
        scanf("%d %d", &a, &b);
        merge2(a, b);
    }
    len = 0;

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j < i; ++j) {
            int p1 = find1(i), p2 = find2(i);
            int tp1 = find1(j), tp2 = find2(j);

            if ((p1 != tp1) && (p2 != tp2)) {
                merge(i, j);
                result[len++] = (ND){j, i};
            }
        }
    }

    printf("%d\n", len);
    for (int i = 0; i < len; ++i) {
        printf("%d %d\n", result[i].x, result[i].y);
    }
    return 0;
}

결과

Contest	Start time	Rank	Solved	Rating change	New rating
#738 (Div. 2)	2021/8/15 23:35	3744	3	+3	1421