ABC341 F - Breakdown

Competitive Programming C++ AtCoder Algorithms

2024-02-17

공식 에디토리얼

문제 링크
https://atcoder.jp/contests/abc341/tasks/abc341_f

원문 링크
https://atcoder.jp/contests/abc341/editorial/9319

정점 \(v\) 에만 말이 \(1\)개 놓여져 있고 다른 정점에는 말이 놓여 있지 않은 상태에서 몇 번 조작이 가능한지, 즉 정점 \(v\)의 말 \(1\)개가 조작 횟수에 기여하는 최댓값 \(\mathrm{dp}[v]\)를 모든 정점 \(v = 1, 2, …, N\)에 대해 구하면 이 문제의 답인 \(\sum_{v = 1}^N \mathrm{dp} \times A_v\)를 구할 수 있습니다.
이제 \(\mathrm{dp}[*]\)를 dp로 구하는 방법을 생각해봅시다.

어떤 정점 \(v\)로부터 말을 꺼내어 집합 \(S\)에 속한 정점 각각에 말을 놓는다고 하면 각 정점 \(u \in S\)에 놓인 말로부터 시작하는 조작이 이후 \(\mathrm{dp} [u]\)번 가능하며, 놓은 말 전체로부터 시작해서 합계 \(\sum_{u \in S} \mathrm{dp} [u]\)번의 조작이 이후 가능합니다. 따라서 조작 횟수를 최대화하려면 \(\sum_{u \in S} \mathrm{dp} [u]\)가 최대가 되는 \(S\)를 고르면 되며,

\[\begin{align} \mathrm{dp} [v] = 1 + \max_S \sum_{u \in S} \mathrm{dp} [u] \end{align}\]

입니다. 여기서 \(S\)는 \(v\)에 인접한 몇 개의 정점만으로 이루어진 집합(공집합이어도 됩니다)이고 \(\sum_{u \in S} W_u < W_v\)를 만족하는 것 모두를 알 수 있습니다.

\(S\)는 \(W_u < W_v\)를 만족하는 정점 \(u\)밖에 포함할 수 없는 것으로부터, 식(1)의 우변도 \(W_u < W_v\)를 만족하는 정점\(u\)들만 존재하므로, \(\mathrm{dp} [v]\)의 값은 \(W_u\)의 작은 \(v\)로부터 순차적으로 구해갈 수 있습니다.

또한, 어떤 고정된 \(v\)에 대해 식(1)의 우변을 구하는 문제는

\(v\)에 인접한 모든 정점\(u_1, u_2, …, u_{\mathrm{deg}(v)}\)에 대해 \(u_i\)의 가치가 \(\mathrm{dp} [u_i]\), \(u_i\)의 비용이 \(W_u_i\)로 고정되었을 떄
비용의 합이 \(W_v\)미만인 제약으로 가치의 합을 최대화하는 문제

인 배낭 문제로 간주해 풀 수 있으며, 이는 dp로 \(O(\mathrm{deg}(v) \times W_v)\)에 풀 수 있습니다.

모든 정점에 대해 위 배낭 문제를 푼다고 가정해도

\[\sum_{v = 1}^N \mathrm{deg}(v)W_v \leq W_{\max} \sum_{v = 1}^N \mathrm{deg}(v) = W_{\max} \times 2M\]

이므로,(단, \(W_{\max} := \max\{W_1, W_2, …, W_N\}\)) 이 문제는 \(O(MW_{\max})\)에 풀 수 있습니다.