Codeforces Round #1051 (Div. 2) 후기

A. All Lengths Subtraction

풀이 보기

풀이

연산을 총 $n$번, 그 때마다 구간을 정해서 구간 내의 모든 수를 $1$ 빼야한다. 구간의 길이는 $1$부터 계속 증가하여 최종적으로는 $n$까지 늘어난다. 주어지는 배열은 순열이므로, $1$부터 $n$까지 1개씩 존재하는 배열임을 기억하자.

가장 큰 수가 $n$이고 연산의 횟수도 $n$이므로, 가장 큰 원소 $n$은 매 연산마다 구간 내에 포함되어야한다. 이 때 첫 연산에서는 구간의 길이가 $1$이므로 가장 큰 원소가 선택되어야 한다.

문제는 그 다음이다. 1번의 연산 뒤에 $n$은 $n-1$이 된다. 그럼 배열 안에는 $n-1$이 2개 존재하는 상태가 되었다. 이 때 다음 연산에서도 $n-1$들은 구간 내에 포함되어야할 것이다. 이 때 연산에서 사용하는 구간의 길이는 $2$가 되었으므로, 두 값을 모두 포함하기 위해서는 처음에 $n$과 $n-1$이 서로 인접해있었어야한다는 것을 알 수 있다.

그리고 이걸 끝까지 반복하여 배열의 조건을 짐작할 수 있다. “가장 큰 수부터 차례로 확인할 때, 그 수들은 항상 인접한 시퀀스 형태로 나타나야한다”. 이 조건을 확인하는 코드를 구현하면 된다. 가장 큰 원소 $n$의 위치를 $idx$로 두고, $left = right = idx$를 초기 위치로 지정한다. 이 다음 $n-1$의 위치가 $left - 1$ 또는 $right + 1$에 있는지 검사하고, 있으면 그 위치로 범위를 재지정한다. 없었다면 불가능한 상태이므로 NO를 출력. 이 과정이 끝까지 지났어도 조건에 위배되지 않았다면 YES를 출력하면 된다.

코드

#include <stdio.h>

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

typedef long long ll;
typedef unsigned long long ull;

#define MAX_IDX (int)(100)

/* variable */
int arr[MAX_IDX];
int n;

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

/* read_input */
void read_input() {
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        scanf("%d", arr + i);
    }
    return;
}

/* solve */
bool solve() {
    int idx = 0;
    for (int i = 1; i < n; ++i) {
        if (arr[i] > arr[idx]) {
            idx = i;
        }
    }

    int left = idx, right = idx;
    for (int i = n - 1; i >= 1; --i) {
        if (left >= 1 && arr[left - 1] == i) {
            left = left - 1;
        } else if (right < n - 1 && arr[right + 1] == i) {
            right = right + 1;
        } else {
            return false;
        }
    }

    return true;
}

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        read_input();
        printf("%s\n", solve() ? "YES" : "NO");
    }
    return 0;
}

B. Discounts

풀이 보기

풀이

오랜만에 그리디 문제가 나온 것 같다. 각 물품의 가격은 정해져있으므로, 할인을 받지 않았을 때의 최종 가격은 이미 정해져있다. 그럼 우리는 할인을 최대한 받아야 값을 제일 적게 지불할 수 있다.

할인을 가장 많이 받기 위해서는, 가능한 비싼 물품의 가격을 $0$으로 만들어야함은 자명하다. 즉, 각 물품의 가격을 비오름차순 정렬, 바우처의 물품 갯수를 비내림차순으로 정렬한 다음, 바우처가 할인해주는 물품의 가격을 빼는 방식으로 구현하면 된다. 물품의 가격을 비오름차순으로 정렬하였기 때문에, 할인이 가능한 물품들 중 가장 가격이 비싼 물품이 자동적으로 선택되고 할인된다. 매우 간단한 문제였다고 생각한다.

코드

#include <stdio.h>
#include <stdlib.h>

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

typedef long long ll;
typedef unsigned long long ull;

#define MAX_IDX (int)(2e5)
ll price[MAX_IDX];
int voucher[MAX_IDX];
int n, k;

int asc(const void* a, const void* b) {
    int x = *(int*)a, y = *(int*)b;

    if (x > y) {
        return 1;
    } else if (x == y) {
        return 0;
    } else {
        return -1;
    }
}
int desc(const void* a, const void* b) {
    int x = *(int*)a, y = *(int*)b;

    if (x > y) {
        return -1;
    } else if (x == y) {
        return 0;
    } else {
        return 1;
    }
}

void read_input() {
    scanf("%d %d", &n, &k);
    for (int i = 0; i < n; ++i) {
        scanf("%lld", price + i);
    }
    for (int i = 0; i < k; ++i) {
        scanf("%d", voucher + i);
    }
    return;
}

ll solve() {
    qsort(price, n, sizeof(ll), desc);
    qsort(voucher, k, sizeof(int), asc);

    ll cost = 0ULL;
    for (int i = 0; i < n; ++i) {
        cost += price[i];
    }

    ll total_used_item = 0;
    for (int i = 0; i < k; ++i) {
        if (total_used_item + voucher[i] > n) {
            break;
        } else {
            total_used_item += voucher[i];
            cost -= price[total_used_item - 1];
        }
    }

    return cost;
}

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        read_input();
        printf("%lld\n", solve());
    }
    return 0;
}

C. Max Tree

풀이 보기

풀이

트리의 각 원소에 순열의 수 하나씩을 모두 할당하여 기여값을 최대화하는 것이 목적이다. 트리의 구조에 의해, 기여값이 항상 최대가 되도록 순열의 값을 부여할 수 있음은 자명하다. 즉, 항상 기여값이 큰 쪽으로 각 원소에 순열값을 할당해주어야한다는 문제로 생각할 수 있다.

각 수들의 대소비교가 되어있을 때, 각 수에 원소를 부여한다는 점은 위상정렬 문제의 표본형이라고 할 수 있다. 그래서 그대로 구현했다. 애초에 문제에 함정 요소가 아예 없다시피해서 이 문제가 위상정렬 문제라는 것을 파악한 뒤부터는 어려운 점이 없었다.

코드

#include <stdio.h>
#include <stdlib.h>

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

typedef long long ll;
typedef unsigned long long ull;

typedef struct Node {
    int idx;
    struct Node* next;
} ND;

#define MAX_IDX (int)(2e5)
int n = 1;

ND* adj_matrix[MAX_IDX + 1];
int deg[MAX_IDX + 1];
int q[MAX_IDX + 1];
int front, rear;
int ans[MAX_IDX + 1];

void init() {
    for (int i = 0; i <= n; ++i) {
        deg[i] = 0;
        adj_matrix[i] = NULL;
    }
    front = rear = 0;
    return;
}

void insert(int a, int b) {
    ND* newNode = (ND*)malloc(sizeof(ND));
    newNode->idx = b, newNode->next = adj_matrix[a];
    adj_matrix[a] = newNode;
    return;
}

void read_input() {
    scanf("%d", &n);
    for (int i = 0; i < n - 1; ++i) {
        int u, v, x, y;
        scanf("%d %d %d %d", &u, &v, &x, &y);

        if (y > x) {
            int temp = u;
            u = v;
            v = temp;
        }

        // edge[i] = (ED){u, v};
        insert(u, v);
        deg[v] += 1;
    }
    return;
}

void solve() {
    int tmp = n;
    for (int i = 1; i <= n; ++i) {
        if (deg[i] == 0) {
            ans[i] = tmp--;
            q[rear++] = i;
        }
    }

    while (front < rear) {
        int cur_idx = q[front++];
        // printf("cur_idx : %d\n", cur_idx);
        for (ND* cur = adj_matrix[cur_idx]; cur != NULL; cur = cur->next) {
            if (--deg[cur->idx] == 0) {
                ans[cur->idx] = tmp--;
                q[rear++] = cur->idx;
            }
        }

        if (tmp == 0){
            break;
        }
    }

    for (int i = 1; i <= n; ++i) {
        printf("%d ", ans[i]);
    }
    printf("\n");
    return;
}

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        init();
        read_input();
        solve();
    }
    return 0;
}

결과

Contest	Start time	Rank	Solved	Rating change	New rating
#1051 (Div. 2)	2025/9/17 23:35	3606	3	-19	1547

D번 문제의 조건에 의해 무조건 DP를 활용하여 푸는 문제임은 파악했지만, 점화식을 계산해내지 못해서 문제 해결에는 실패했다. 1시간 넘게 고민했었는데 가장 기본적인 case를 고려하지 못했었다. 예제에서 오답이 나와서 다행이지, 만약 예제에서 정답이라고 출력되었다면 의미없는 제출만 반복하고 있었을지도 모르겠다.