Codeforces Round #1048 (Div. 2) 후기

A. Maple and Multiplication

풀이 보기

풀이

풀이는 아래 3가지로 정리 가능하다.

• 만약 $a = b$라면, 연산이 필요 없다. $ans = 0$
• 만약 $a ~ \vert ~ b$ 또는 $b ~ \vert ~ a$라면, 제수에 몫만큼 곱해주면 $a=b$를 얻어낼 수 있다. $ans = 1$
• 그 이외의 상황에서는, $a = a \times b$, $b = b \times a$를 해주면 $a=b$를 항상 얻어낼 수 있다. $ans = 2$

위 case를 제외한 경우는 없으므로, 각 case에 맞는 상황을 찾고 답을 출력해주면 된다.

코드

#include <stdio.h>

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        int a, b;
        scanf("%d %d", &a, &b);

        if (a == b) {
            printf("0\n");
        } else if (a % b == 0 || b % a == 0) {
            printf("1\n");
        } else {
            printf("2\n");
        }
    }
    return 0;
}

B. Cake Collection

풀이 보기

풀이

각 오븐에서 만들어지는 케이크는 가져가지 않으면 누적된다는 것이 문제의 핵심이다.

우선 다른 문제를 생각해보자. 전체 $m$초 중에서 1번의 행동 기회만 주어질 때, “한 번의 행동으로 최대한 많이” 가져가는 것을 목표로 삼아보자. 이 문제의 정답은 $\max([a_1, a_2, \cdots, a_n]) \times m$이 된다. 만약 $max([a_1, a_2, \cdots, a_n]) = a_i$라고 하면, 우린 마지막 순간에 $i$번째 오븐에 가서 케이크를 모두 가져오면 케이크를 최대로 가져오는 것이다. 1번의 행동으로 최대의 케이크를 얻기 위해서는 1초당 최대의 케이크를 만들어내는 오븐인 $i$를 마지막에 방문해야한다는 사실을 알 수 있다.

이걸 고려하며 다시 원래 문제를 생각해보자. $m$초때는 $i$번째 오븐을 방문할 것이므로, 그 이전에는 $i$번째 오븐을 방문할 필요가 없다. 그럼 문제의 정답 $ans$를 아래와 같이 작은 문제로 분할할 수 있는 기회가 보인다.

\[\begin{aligned} ans_m &= ans_{m-1} + \max([a_1, a_2, \cdots, a_n]) \times m\\ &= ans_{m-2} + \max([a_1, a_2, \cdots, a_n] - [a_i]) \times (m-1) + \max([a_1, a_2, \cdots, a_n]) \times m \\ &\cdots \end{aligned}\]

계속해서 작은 문제로 분할해나갈 수 있으며, 그 때의 최종 정답은 $\sum_{i=0}^{\min(m, n)} a_i \times (m - i)$이 된다. 이 때 배열 $a$는 비오름차순 정렬이 되어있다고 가정한다.

결론으로는, 문제 해결을 위해서는 오븐의 케이크 생성량 $a$를 먼저 비오름차순으로 정렬하고, 위 수식의 값을 도출해내면 된다.

여담인데, 처음 코드를 제출했을 때는 계속 오답을 받았다. $\max(time~\times~cakes) \leq 10^{13}$이라 계산 중 overflow가 발생하는 것이라고 생각해서 long long도 활용해보았지만 계속 오답을 받았다. 결국 이 문제에서 -4 페널티를 받고, overflow 고려를 딱히 하지 않아도 되는 C++로 코드를 다시 짜서 제출하였다.

하지만, 이후 다시 풀어보니 문제는 overflow가 아닌 정렬에 있었다. C에서는 정렬을 돕기 위한 qsort라는 함수가 있는데, 여기에 사용하는 cmp 사용자 정의 함수를 만드는 과정에서 문제가 있었다. 나는 지금까지 오름차순 정렬을 위해 아래와 같이 cmp 함수를 정의했었다.

int cmp(ll* a, ll* b) {
    return *a > *b; // 오름차순 정렬
}

문제에서 원하는 바는 비오름차순이었으므로 반대로 정렬해주면 된다고 생각했다.

int cmp(ll* a, ll* b) {
    return *a < *b; // 비오름차순 정렬
}

하지만 결과는 오답이었다. cmp 함수를 <stdlib.h>에 있는 형식에 맞춰서 다시 작성하니 그때서야 통과되는 것을 확인할 수 있었다. 이 문제에서부터, 나는 “contest는 C++로 코드를 짤 것”을 다짐하게 되었다. C++ 언어 연습을 좀 하고, 다음 contest부터는 C++로 참여하려한다.

코드

#include <stdio.h>

typedef long long ll;

#define MAX_IDX (ll)(1e5)

ll arr[MAX_IDX];

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

int desc(const void* p, const void* q) {
    ll x = *(const ll*)p, y = *(const ll*)q;
    if (x < y) return 1;
    if (x > y) return -1;
    return 0;
}


int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        int n, m;
        scanf("%d %d", &n, &m);
        for (int i = 0; i < n; ++i) {
            scanf("%lld", arr + i);
        }
        qsort(arr, n, sizeof(ll), desc);

        ll ret = 0;
        for (int i = 0; i < min(m, n); ++i) {
            ret += (arr[i] * (m - i));
        }
        printf("%lld\n", ret);
    }
    return 0;
}

C. Cake Assignment

풀이 보기

풀이

가능한 연산은 아래 2가지다.

• OP1 : Chocola이 Vanilla에게 케이크를 절반 준다
• OP2 : Vanilla가 Chocola에게 케이크를 절반 준다

현재 상태 $(A, B)$를 (Chocola가 가진 케이크 수, Vanilla가 가진 케이크 수)로 정의하자. 이 때 문제의 정의에 의해 $A + B = 2^{k+1}$이다. 이제 각 연산을 다시 생각해보자. 현재 상태를 $(A, 2^{k+1} - A)$라고 했을 때, 각 연산의 결과는 아래와 같아진다.

• OP1 : $(A, 2^{k+1} - A) \rightarrow (\frac{A}{2}, 2^{k+1} - \frac{A}{2})$
• OP2 : $(A, 2^{k+1} - A) \rightarrow (2^k + \frac{A}{2}, 2^k - \frac{A}{2})$

우리의 목표는 Chocola의 케이크 $2^k$개를 $x$개로 만드는 과정을 찾는 것이다. 연산을 한 번 할때마다 Chocola의 케이크 $A$는 $\frac{A}{2}$ 또는 $\frac{A}{2} + 2^k$이 된다. 완전탐색으로 답을 찾을 수 있을 것 같지만, 문제에서 depth의 최댓값은 $120$번이라고 얘기하고 있다. $2^{120}$가지의 탐색은 불가능할 것이다.

변경된 연산을 다시 한 번 자세히 보면, Chocola가 가지고 있던 케이크 $A$는 항상 $\frac{A}{2}$로 바뀌는 것을 볼 수 있다. OP2 연산에서는 $2^k$가 추가되는 것을 볼 수 있다. 이걸 비트로 다시 생각해보면, $A$를 한칸 오른쪽으로 민 다음, 연산에 따라서 $2^k$를 추가하는 것으로도 이해할 수 있다. $2^k$를 추가하는 것은 가장 왼쪽에 비트를 on하는 것과도 같다!

$k$가 주어졌을 때, Chocola가 가진 케이크의 초기값은 $2^k$개이다. $k = 4$일 때를 예시로 들면, 이걸 비트로 표현하면 $10000$이 된다. 비트 $k + 1 = 5$자리로 표현 가능하다. 연산을 아무리 진행해도 비트 자릿수는 최대 $5$자리이다. 이 때 $2^k$가 추가되는 것은 비트의 가장 왼쪽 자리가 on되는 것이라고 얘기할 수 있다.

즉, 초기 상태 $1000\cdots00$에서 원하는 결과값 $x$를 만들어내기 위해서 각 상태마다 비트를 오른쪽으로 1칸 민 다음 필요에 따라 가장 왼쪽에 비트를 추가해나가는 과정으로 결과를 찾아내면 된다. 이 방법을 구현한 코드가 아래 정답과 같다.

에디토리얼에는 다른 풀이가 존재한다. 에디토리얼의 풀이를 정리해보면 다음과 같다.

• 어떤 상태 $(a, b)$가 주어졌을 때, 그 이전 상태로 되돌아가는 방법은 단 1개 존재한다
  • $a < b$라면 OP1이 실행되었었다는 의미이며, 이전 상태는 $(2a,b - a)$였다
  • $a > b$라면 OP2가 실행되었었다는 의미이며, 이전 상태는 $(a - b, 2b)$였다

끝 상태를 $(x, 2^{k+1} - x)$, 시작 상태를 $(2^k, 2^k)$라고 할 수 있으므로, 단계를 역추적해가며 시작 상태로 되돌아갔을 때, 지나온 연산들을 반대로 출력해내면 정답을 얻어낼 수 있다.

코드

#include <stdio.h>

typedef long long ll;

#define MAX_IDX 120

int ret[MAX_IDX];

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        int k;
        ll x;
        scanf("%d %lld", &k, &x);

        // rightmose bit finding
        int cnt;
        for (cnt = 0; (x & 1) == 0; ++cnt) {
            x >>= 1;
        }
        printf("%d\n", k - cnt);

        for (int i = 0; i < k - cnt; ++i) {
            if ((x & 2) == 0) {
                printf("1 ");
            } else {
                printf("2 ");
            }
            x >>= 1;
        }
        printf("\n");
    }
    return 0;
}

E1. Maple and Tree Beauty (Easy Version)

풀이 보기

풀이

우선 문제에서 주어진 입력으로 트리 구조를 만들 수 있다. 결론부터 말하면 트리 구조는 딱히 저장해둘 필요는 없고, ROOT의 level을 $0$이라고 하고, 각 level에 있는 노드의 수만 있으면 답을 찾아낼 수 있다. 트리를 만드는 과정은 각 level에 있는 노드의 수를 파악하기 위한 과정일 뿐이다. 이 코드에서는 cnt[level] 배열에 level당 노드의 개수를 저장해두도록 하였다.

cnt[] 배열이 만들어졌으면 두 번째로 “길이가 가장 짧은 리프 노드의 level”을 찾는다. min_depth라고 정의된 변수에 저장하며, 가능한 정답의 최댓값을 의미한다. 아무리 최적으로 트리에 라벨링을 하더라도, 구조적으로 min_depth + 1를 넘는 답은 존재할 수 없다. min_depth에 있는 리프 노드의 이름 길이가 min_depth + 1이므로, 리프 노드들의 가장 긴 공통 이름의 길이는 최대 min_depth + 1이 되기 때문이다.

이제 current_level을 $0$부터 min_depth까지, 각 level의 노드들에 같은 라벨을 붙일 수 있는지 검사한다. $0$의 개수가 충분하여 current_level의 모든 노드들을 $0$으로 라벨링할 수 있으면 $0$으로 라벨링하고 다음 level로 넘어간다. $1$로 라벨링할 수 있다면 $1$로 라벨링하고 다음으로 넘어간다. 만약 라벨링 할 수 없다면 그 시점에서 재귀를 종료하며 리턴한다. 이렇게 되면 루트에서부터 prefix를 최대한 같게 지정하는 것처럼 보인다. 문제에서 원하는건 리프노드들의 연속 LCS를 최대화하는 것이었지만, 이 풀이에서는 트리에서의 prefix를 최대화하는 것을 목표로 한다.

왜 이 직관이 가능한 답안일까? 트리라는 구조상, 모든 리프 노드가 같은 라벨링을 가지도록 하려면 가장 위에서부터 똑같은 라벨링을 받는 것이 연속 LCS를 가장 길게 만드는 것이기 때문이다. 그러므로, 중간 단계에 대한 고려는 딱히 하지 않고, 가능한 위에서 같은 level에는 같은 라벨링을 가지도록 하는 것으로 알고리즘의 방향을 정했다.

사용한 방법은 재귀를 활용한 백트래킹. solve() 함수를 구현하여 남아있는 라벨 개수를 $(zeros, ones)$로 정의하고 current_level에 있는 모든 노드들에게 같은 라벨을 부여할 수 있는지 확인한다. 라벨링할 수 있으면 모두 같은 라벨을 부여하고 다음 level로 넘어가도록 구현하였다. 이 방식의 구현 결과는 시간 초과. 생각해보면 최악으로 $O(2^N)$이므로 $2^{1000}$까지의 함수 호출이 필요했을 것 같다.

그럼 이 때 시간을 줄이기 위해 활용할 수 있는 방법이 dp를 활용한 메모이제이션이 되겠다. 이미 1번 계산한 결과값은 dp[][] 배열에 기록해둠으로써 중복 계산 과정을 줄이는 방법이다. $N=1\,000$이므로 dp[][] 크기는 $10^6$칸. 시간에는 충분히 돌아갈 것이라고 생각하고 구현했다. 다행히도, 푸는 방법에는 문제가 없었던 것 같다.

코드

#include <stdio.h>

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

typedef long long ll;
typedef struct QueueNode {
    int idx;
    int dep;
} QN;

#define MAX_IDX (1000 + 1)
const int INF = 987654321;

QN queue[MAX_IDX];
int cnt[MAX_IDX];
int depth[MAX_IDX];
int min_depth;

int dp[MAX_IDX][MAX_IDX];
const int NONE = -1;

int tree[MAX_IDX][MAX_IDX];
const int ROOT = 1;

int n, k;

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

void init() {
    for (int i = 0; i < MAX_IDX; ++i) {
        tree[i][0] = 0;
        cnt[i] = 0;
        for (int j = 0; j < MAX_IDX; ++j) {
            dp[i][j] = NONE;
        }
    }
    min_depth = INF;
    return 0;
}

void calc_depth() {
    depth[ROOT] = 0;
    cnt[0] = 1;

    int front = 0, rear = 0;
    queue[rear++] = (QN){ROOT, 0};

    while (front < rear) {
        QN cur_node = queue[front++];
        for (int i = 1; i <= tree[cur_node.idx][0]; ++i) {
            depth[tree[cur_node.idx][i]] = cur_node.dep + 1;
            cnt[cur_node.dep + 1] += 1;
            queue[rear++] = (QN){tree[cur_node.idx][i], cur_node.dep + 1};
        }

        if (tree[cur_node.idx][0] == 0) {
            min_depth = min(min_depth, cur_node.dep);
        }
    }
    return;
}

int solve(int current_depth, int zeros, int ones) {
    if (current_depth > min_depth) {
        return 0;
    } else if (dp[current_depth][zeros] != NONE) {
        return dp[current_depth][zeros];
    }
    
    int ret = 0;
    if (cnt[current_depth] <= zeros) {
        ret = max(ret, 1 + solve(current_depth + 1, zeros - cnt[current_depth], ones));
    }
    if (cnt[current_depth] <= ones) {
        ret = max(ret, 1 + solve(current_depth + 1, zeros, ones - cnt[current_depth]));
    }
    return dp[current_depth][zeros] = ret;
}

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        init();
        scanf("%d %d", &n, &k);
        for (int i = 2; i <= n; ++i) {
            int a;
            scanf("%d", &a);
            tree[a][++tree[a][0]] = i;
        }
        calc_depth();

        printf("%d\n", solve(0, k, n - k));
    }
    return 0;
}

E2. Maple and Tree Beauty (Hard Version)

풀이 보기

풀이

문제는 그 다음이다. $N=200\,000$으로 제한이 늘어나버린 것. 코드를 그대로 제출하니 컴파일 에러가 발생했고, 그 때의 에러 메세지는 “배열을 할당할 수 없음“이었다. 배열의 크기가 너무 커져버리면 컴파일 단계에서 멈춰버린다는 것을 이 때 처음 알았다.

E1 문제에서 사용한 2차원 int 배열은 2가지가 있다.

• tree[][] : 트리 구조를 도식화하기 위한 배열
• dp[][] : solve() 함수 결과값을 기록하기 위한 배열

사실 tree[][] 배열은 굳이 2차원일 이유가 없다. 연결리스트로 트리를 구현하면 되기 때문. 과정이 조금 귀찮긴 해도, 인접행렬로 만들 수 없는 트리들은 인접리스트를 활용하여 구현하였으니 그 방법을 그대로 가져오자. 하지만 문제는 이 부분이 아니다.

가장 큰 문제는 dp[][] 배열. 지금의 점화식으로는 이 배열의 크기를 줄일 방법이 없다. 그러다 문득 한 가지 생각이 들었다. 문제에서 원하는 해답이 Root에서부터의 연속 LCS였으니, 앞에서 동일한 라벨을 부여할 수 없으면 뒤는 아예 계산할 필요가 없다는 것. 그럼 풀이과정에서 고려해야할 것은 “현재의 depth에서의 라벨링 성공 여부”가 되는 것이고, 현재의 state만 잘 기록해둘 수 있으면 이전 depth에서의 결과를 굳이 저장할 필요가 없다는 것. 해서 current_depth를 잘 기록해둘 수 있으면, dp[][] 배열이 2차원일 이유가 없다! 1차원 배열로 변경한 후 함수 진행을 보도록 하자.

하지만 배열의 크기를 줄였더라도 시간초과가 발생했다. 아무래도 기존의 재귀 DP 방식으로는 문제 해결이 불가능할 것 같다. 현재 시간을 가장 오래 잡아먹는 부분은 solve() 함수에서 dp[i] 배열의 업데이트 부분일 것이다. dp[i]를 “$i$개의 0 라벨을 사용하고, 나머지는 1로 라벨링할 때 같은 depth의 노드들은 모두 같은 라벨을 붙일 수 있는가“를 나타내고 있다. 이 부분에서 dp[i] = true인 부분들 모두에서 현재 depth의 노드 개수가 $a$개라고 할 때 dp[i+a] = true로 바꿔주는 과정이 필요한데, 이 부분에서 $O(N)$이 계속 필요하므로 최악으로 $O(N^2)$이 불가피하게 된 것 같다. dp[] 배열의 업데이트를 $O(1)$로 줄여낼 수 있으면 빠르게 해결할 수 있을 것 같다.

그렇게 활용하게 된 방법이 bit 연산을 활용한 저장법이다. 타입을 unsigned long long으로 변경하고 dp[i] |= dp[i + a]를 하면 같은 연산을 $64$배 빠르게​ 계산해낼 수 있다. 다만 수의 범위가 $N = 200\,000$이므로 변수 하나로 해결할 수는 없으니, 블럭 단위로 시간을 줄여낼 수 있을 것이다. 이 방법으로 구현을 시도하여 시간이 줄었는지 확인하고, 이래도 시간초과가 걸린다면 다른 최적화 방법도 고려해야할 것이다.

20번 테스트케이스에서 틀렸다고 떠서 원인을 분석하니, 사용했던 상수들의 데이터 타입이 원인이었다. unsigned long long을 사용할 때, 즉 64비트 연산을 할 때 상수를 ULL로 지정해주지 않으면 32비트로 취급한다는 것을 이 때 처음 알았다. 앞으로 상수를 활용할 때 오버플로가 난다면 이것을 꼭 고려해야겠다.

코드

#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 TreeNode {
    int idx;
    struct TreeNode* next;
} TN;
typedef struct QueueNode {
    int idx;
    int dep;
} QN;

#define MAX_IDX (200000 + 1)

TN* tree[MAX_IDX];
const int ROOT = 1;
const int NONE = -1;

int cnt_of_depth[MAX_IDX];
int min_leaf_depth;

ull dp[MAX_IDX];
ull tmp[MAX_IDX];

int n, k;

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

void init() {
    for (int i = 0; i < MAX_IDX; ++i) {
        tree[i] = NULL;
        cnt_of_depth[i] = 0;
        dp[i] = 0;
    }
    min_leaf_depth = MAX_IDX + 1;
    return;
}

void connect_edge(int x, int p) {
    TN* newNode = (TN*)malloc(sizeof(TN));
    newNode->idx = x;
    newNode->next = tree[p];
    tree[p] = newNode;
    return;
}

void read_input() {
    scanf("%d %d", &n, &k);
    for (int i = ROOT + 1; i <= n; ++i) {
        int p;
        scanf("%d", &p);
        connect_edge(i, p);
    }
    return;
}

void preprocess() {
    QN queue[MAX_IDX + 1];
    int front = 0, rear = 0;
    queue[rear++] = (QN){ROOT, 0};

    while (front < rear) {
        int cnt_of_level = rear - front;
        bool isLeafExists = false;
        QN node = queue[front];
        cnt_of_depth[node.dep] = cnt_of_level;

        for (int i = 0; i < cnt_of_level; ++i) {
            node = queue[front++];
            if (tree[node.idx] == NULL) {
                isLeafExists = true;
            } else {
                for (TN* cur = tree[node.idx]; cur != NULL; cur = cur->next) {
                    queue[rear++] = (QN){cur->idx, node.dep + 1};
                }
            }
        }

        if (isLeafExists == true) {
            min_leaf_depth = node.dep;
            break;
        }
    }
    return;
}

void bitset_left_shift(ull* out, ull* in, int w, int blocks) {
    int word = w >> 6;
    int bit = w & 63;

    // init
    for (int i = 0; i < blocks; ++i) {
        out[i] = 0ULL;
    }

    // shift
    if (w == 0) {
        for (int i = 0; i < blocks; ++i) {
            out[i] = in[i];
        }
    } else if (bit == 0) {
        for (int i = blocks - 1; i >= word; --i) {
            out[i] = in[i - word];
        }
    } else {
        for (int i = blocks - 1; i >= word + 1; --i) {
            ull hi = in[i - word];
            ull lo = in[i - word - 1];
            out[i] = (hi << bit) | (lo >> (64 - bit));
        }
        if (blocks - 1 >= word) {
            out[word] = in[0] << bit;
        }
    }

    // used upper bound = k
    int last_bits = (k & 63);
    if (last_bits) {
        ull m = (last_bits == 63) ? (~0ULL) : ((1ULL << (last_bits + 1)) - 1ULL);
        out[blocks - 1] &= m;
    }

    return;
}

bool any_bit_in_range(ull* bs, int L) {
    if (L < 0) {
        L = 0;
    }
    if (L > k) {
        return false;
    }

    int lb = L >> 6, rb = k >> 6;
    int lo = L & 63, ro = k & 63;

    if (lb == rb) {
        ull m = ((ro == 63) ? (~0ULL) : ((1ULL << (ro + 1)) - 1ULL));
        m &= ((~0ULL) << lo);
        return (bs[lb] & m) != 0;
    } else {
        ull left_mask = (~0ULL) << lo;
        if ((bs[lb] & left_mask) > 0) {
            return true;
        }

        for (int i = lb + 1; i < rb; ++i) {
            if (bs[i] > 0) {
                return true;
            }
        }

        ull right_mask = (ro == 63) ? (~0ULL) : ((1ULL << (ro + 1)) - 1ULL);
        if ((bs[rb] & right_mask) > 0) {
            return true;
        }

        return false;
    }
}

int solve(int zeros, int ones) {
    int blocks = (k >> 6) + 1;
    dp[0] = 1ULL;

    int total_used = 0;
    int ret = 0;

    for (int d = 0; d <= min_leaf_depth; ++d) {
        int w = cnt_of_depth[d];

        bitset_left_shift(tmp, dp, w, blocks);
        for (int i = 0; i < blocks; ++i) {
            dp[i] |= tmp[i];
        }
        total_used += w;

        int LB = total_used - ones;

        if (any_bit_in_range(dp, LB) == true) {
            ret += 1;
        } else {
            break;
        }
    }

    return ret;
}

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

결과

Contest	Start time	Rank	Solved	Rating change	New rating
#1048 (Div. 2)	2025/9/8 23:35		5		1499

문제 D번에서 풀이하는데 심각한 오류가 발견되었고, 컨테스트가 unrated로 변경되었다.

Div. 2에서 최고 성적을 냈다고 자신할 수 있었는데, rate를 받지 못한 것은 많이 슬펐다.