Codeforces Round #885 (Div. 2) 후기

A. Vika and Her Friends

풀이 보기

풀이

Vika가 친구들을 피해 무한히 도망칠 수 있는지 판별하는 문제이다. 게임이론같이 어려운 생각은 버리도록 하자. 친구들은 Vika의 행동을 보고 최적의 행동을 취한다. 즉 게임이 무한히 진행된다면 언젠가는 잡히게 된다. 그렇다면 애초에 잡힐 수 없는 전제에서만 게임이 무한히 진행될 것이다.

여기서 한가지 생각해볼 수 있는건, Vika와 친구들이 모두 무조건 1칸씩 이동해야한다는 것이다. 즉 인접하고 있으면 애초에 같은 칸에 존재할 수가 없다. 마찬가지로, 날일자로 존재하더라도 절대로 잡을 수 없다. 일반화하면, “Vika와 홀수 칸 떨어져있는 친구들은 Vika를 절대로 잡을 수 없다”!

반대로 얘기하면, Vika와 짝수 칸 떨어져있는 친구들은 Vika를 잡을 수 있다. 그것만 판별하면 된다.

코드

#include <stdio.h>

typedef char bool;
const bool true = 1;
const bool false = 0;

int main() {
    int t;
    scanf("%d", &t);

    while (t--) {
        int n, m, k;
        scanf("%d %d %d", &n, &m, &k);

        int x, y;
        scanf("%d %d", &x, &y);

        bool canCaught = false;
        for (int i = 0; i < k; ++i) {
            int a, b;
            scanf("%d %d", &a, &b);
            if ((x + y) % 2 == (a + b) % 2) {
                canCaught = true;
            }
        }

        if (canCaught == true) {
            printf("NO\n");
        } else {
            printf("YES\n");
        }
    }

    return 0;
}

B. Vika and the Bridge

풀이 보기

풀이

한번에 뛰어넘어야하는 칸의 수를 최소화하는 문제이다. 여기서 우리는 칸의 색깔을 딱 한번 바꿀 수 있다.

기준을 색깔로 정하고 생각해보자. 칸의 색깔을 변경하지 않는다고 가정하면, 각 색깔에 대해 뛰어넘어야하는 칸의 수를 계산해낼 수 있고, 그것들 중 최솟값을 출력하면 될 것이다.

하지만 칸의 색깔을 하나 바꿀 수 있다는 것이 난이도를 조금 더 올리게 된다. 간단히 설명하겠다. 특정 색깔에 대해 뛰어넘는 칸의 최댓값을 줄일려면 뛰어넘는 칸의 최대 구간을 반으로 나눌 수 있도록 중간을 색칠하는 것이다. 이렇게 하면 그 색깔의 간격은 $\frac{length}{2}$가 될 것이다. 이게 최대일 수도 있고, 2번째로 큰 간격이 최대가 될 수도 있다. 이 값들 중 최솟값을 찾으면 될 것이다.

코드

#include <stdio.h>

#define MAX_IDX 200001

typedef struct Node {
    int last;
    int first, second;
} ND;

ND grid[MAX_IDX];

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

int main() {
    int t;
    scanf("%d", &t);

    int n, k = 0;
    while (t--) {
        for (int i = 1; i <= k; ++i) {
            grid[i].last = 0;
            grid[i].first = -1, grid[i].second = -1;
        }
        int result = MAX_IDX + 1;

        scanf("%d %d", &n, &k);
        for (int i = 1; i <= n; ++i) {
            int a;
            scanf("%d", &a);

            int temp = i - grid[a].last;
            if (grid[a].first < temp) {
                grid[a].second = grid[a].first;
                grid[a].first = temp;
            } else if (grid[a].second < temp) {
                grid[a].second = temp;
            }

            grid[a].last = i;
        }
        for (int a = 1; a <= k; ++a) {
            int i = n + 1;

            int temp = i - grid[a].last;
            if (grid[a].first < temp) {
                grid[a].second = grid[a].first;
                grid[a].first = temp;
            } else if (grid[a].second < temp) {
                grid[a].second = temp;
            }

            // TODO
            if (grid[a].second == -1) {
                grid[a].second = MAX_IDX + 2;
            }
            temp = max((grid[a].first + 1) / 2, grid[a].second) - 1;
            if (temp < result) {
                result = temp;
            }
        }

        printf("%d\n", result);
    }

    return 0;
}

결과

Contest	Start time	Rank	Solved	Rating change	New rating
#885 (Div. 2)	2023/7/16 23:35	2092	2	+26	1481