KMO

트리로 해석하기

$K$개의 기호를 사용하는 접두어 코드에서 코드 길이들을 $b_i$라 하면 크라프트 부등식 $\sum K^{-b_i}\leq1$을 만족한다. 역도 성립한다. 길이를 오름차순으로 정렬하고 깊이별로 남는 자리를 $K$개씩 확장하면, 부등식이 성립하는 동안 각 길이에 해당하는 잎을 배치할 수 있다.

따라서 최대 $K$개의 자식을 갖는 루트 트리에서 가중치 $a_i$인 잎의 깊이 $b_i$를 정하고, 가중치와 깊이의 곱의 합을 최소화하는 문제이다. 가중치가 $0$인 잎도 실제 원소이므로 제거하면 안 된다.

허프만 병합

$N=1$이면 $b_1=0$이다. 이하에서는 $N\geq2$라 하자. 모든 내부 정점이 정확히 $$개의 자식을 갖는 트리의 잎 개수 은 을 만족한다. 따라서 가중치가 인 가상 잎을

$$d=(K-1-(N-1)\bmod(K-1))\bmod(K-1)$$

개 추가한다. 이 가상 잎을 추가해도 최소 비용은 변하지 않는다. 이를 보려면 최적 트리의 단항 정점을 없애고 내부 정점을 가능한 한 줄이는 형태를 생각하면 된다. 비가득 내부 정점들을 가장 깊은 곳에 모아 하나만 남길 수 있고, 그 부족한 자리를 $d$개의 가상 잎으로 채울 수 있다. 잎을 더 얕게 옮기는 과정은 비음수 가중치의 비용을 증가시키지 않는다.

가장 깊은 형제 잎들에 가장 작은 $K$개의 가중치를 배치하는 최적해가 존재한다. 더 작은 가중치가 더 얕은 곳에 있다면 두 잎을 교환해도 비용이 증가하지 않기 때문이다. 이 $K$개를 하나의 잎으로 합치고 가중치를 합으로 바꾸면, 원래 비용은 축약한 트리의 비용에 그 합을 더한 값이다. 이를 반복하면 최소 힙으로 구현하는 $K$진 허프만 알고리즘을 얻는다.

가상 잎을 실제로 생성할 필요는 없다. 첫 병합에서 실제 잎을

$$r=K-d=2+(N-2)\bmod(K-1)$$

개 합치고, 이후에는 매번 $K$개를 합치면 된다. $K>N$이면 $r=N$이다. $N-1$이 $$의 배수이면 첫 병합에서도 개를 합쳐야 한다.

각 병합에서 꺼낸 정점들의 부모를 새 정점으로 기록한다. 부모의 번호가 항상 더 크므로, 정점 번호를 역순으로 순회하여 깊이를 구하면 재귀 없이 답을 복원할 수 있다. 원래 입력 순서에 맞추어 잎의 깊이를 출력한다.

복잡도와 정수 범위

실제 원소로 만든 트리의 내부 정점 수는 $N-1$ 이하이며, 모든 내부 정점의 자식 수는 $2$ 이상이다. 따라서 모든 잎의 깊이는 $N-1$ 이하이다. 시간 복잡도는 $O(N\log N)$, 공간 복잡도는 이다.

병합 가중치는 $\sum a_i\leq2\cdot10^{14}$이다. 모든 깊이를 $\lceil\log_K N\rceil$로 정하는 것도 가능하므로 최적 비용은 이다. signed 64-bit 정수로 충분하다. 자체를 계산할 필요는 없다.

부분 점수

서브태스크 1에서는 가중치를 내림차순으로 정렬하고 깊이를 오름차순으로 열거한다. 교환 논증으로 이 순서의 최적해가 존재한다. $0$부터 $N-1$까지의 비감소 깊이열은 $\binom{2N-1}{N}$개이며, 각 열의 조건을 에 검사할 수 있다. 따라서 완전탐색으로 충분하다.

서브태스크 2는 이진 허프만 코딩이다. 매번 가장 작은 두 가중치를 합치면 되며, 시간 복잡도는 $O(N\log N)$이다.

체커의 정확한 조건 검사

깊이별 잎 개수를 세고, 깊이 $0$에서 자리 수를 $1$로 시작한다. 현재 깊이의 잎 개수가 자리 수보다 크면 부등식을 위반한다. 사용한 자리를 뺀 뒤 다음 깊이로 갈 때 $K$배 한다. 자리 수는 $N+1$에서 잘라도 된다. 전체 잎이 $N$개뿐이므로 이를 초과하는 정확한 개수는 판정에 영향을 주지 않는다.

체커는 별도로 구한 최적 비용을 예산으로 두고 각 $a_i b_i$를 빼기 전에 초과 여부를 나눗셈으로 검사한다. 오답 출력의 거대한 비용을 먼저 합산하지 않는다.

Solution written by GPT6