ABC359 F - Tree Degree Optimization
Competitive Programming C++ AtCoder
2024-06-25
공식 에디토리얼
문제 링크
https://atcoder.jp/contests/abc359/tasks/abc359_f
원문 링크
https://atcoder.jp/contests/abc359/editorial/10260
트리의 차수 수열 \(d = (d_1, …, d_N)\)으로써 가능한 정수 수열은 다음을 만족하는 것입니다.
- \(d_i \geq 1\)
- \(\sum_{i = 1}^N d_i = 2N - 2\)
(보충 설명: 이 사실은 프뤼퍼 수열(Prüfer sequence) 을 생각해보면 바로 알 수 있습니다. 또는, 총합의 조건으로부터 \(d_i = 1\)을 만족하는 정점이 반드시 존재하므로, 그런 정점 \(i\)와 그 이외의 정점의 간선을 제거하는 것을 생각하면, 귀납법으로 증명할 수 있습니다.)
이 조건을 만족하는 임의의 수열은 트리의 차수 수열으로써 존재 가능하므로, 위의 조건을 만족하는 수열에 대한 비용의 최솟값을 구하면 됩니다.
이는, 비용의 증가량이 \(d_i\)에 대해 단조 증가하는 것으로부터, 그리디 알고리즘으로 풀 수 있습니다.
(보충 설명: 그리디 알고리즘의 정당성은 볼록 함수 끼리의 합성곱을 생각하면 증명됩니다.)
구체적으로는 처음 모든 \(i\)에 대해 \(d_i = 1\)로 초기화하고, \(d_i\)를 \(1\) 늘렸을 때 비용의 증가량이 최소가 되는 \(i\)에 대해 \(d_i\)를 \(1\) 늘리는 것을 \(N - 2\)번 반복하면 됩니다.
이 그리디 알고리즘은 우선순위 큐 등을 이용해 더 빠르게 할 수 있으며, \(O(N \log N)\)에 동작합니다.
꽤나 선방한 라운드
이번엔 E까지 꽤 빠르게 풀어서인지, 지금까지 친 ABC 중에서도 꽤 좋은 성적을 달성했다.
C, D가 평소보다 어려웠음에도 선방.
30분 정도 여유가 있었지만 F, G의 경우엔 역시 아직은 생소하거나 자신이 없는 문제들이라 그냥 E 풀고 껐다.
슬슬 E 풀이도 안정적이 되어가는 느낌이니 다음엔 있는 대로 시간을 활용해볼까.