E - Cookies 解説 by en_translator
Original proposer: kyopro_friends
This problem can be solved by simulating the process of starting from the best combination and compromising little by little, using a priority queue.
By sorting \(A_i\), we may assume that \(A_1\geq A_2 \geq \ldots\).
Represent by a length-\(N\) sequence \((C_1,\dots,C_N)\) the way of choosing where \(C_i\) cookies of the \(i\)-th kind are chosen.
For a choice of cookies \((C_1,\dots,C_N)\), consider a choice that can be written as \((C_1,\dots,C_{i-1},C_{i}-1,C_{i+1}+1,C_{i+2},\dots)\) for some \(i\) with \(C_i\neq 0\); let us call it a one-step compromised choice. The total deliciousness of a one-step compromised choice does not exceed the total deliciousness before compromising, so when enumerating choices in descending order of total deliciousnesses, we do not need to consider a one-step compromised choice before considering the original choice. Also, any choice can be reached by repeatedly compromising by one step.
Therefore, the problem can be solved by managing pairs of the sum of deliciousness and the choice of cookies in a priority queue. Whenever taking out of an element from the queue, insert one-step compromised choices to the queue. This way, the choices can be enumerated in the order of deliciousnesses. Be careful not to insert a choice that is already inserted in the queue. Whenever taking out of an element, at most \(N\) elements is inserted, so the first \(X\) elements can be enumerated in \(O(NX\log(NX))\) time. Thus the problem has been solved.
Similar problem
ABC391F “K-th Largest Triplet”
bonus
Solve the problem with the upper bound of \(N\) being \(10^5\), while the other constraints remaining the same.
Solution
The essential solution is same as the one already described. We change the way of compromising. Consider an operation such that "pull the rightmost non-zero element back to the left" is its inverse operation. For example, we compromise from $(2,2,0,0)$ to $(2,1,1,0)$ and $(1,3,0,0)$, and from $(2,0,2,0)$ to $(2,0,1,1)$. Since the inverse operation is unique, the path to each choice is also unique, so we no longer have to manage if a choice is already contained in the queue. Moreover, the delta of deliciousness sum is uniquely determined by the position and the value of the rightmost non-zero element and the previous element, which can be managed by $O(1)$-size data. Therefore, the problem can be solved in $O(N\log N+X\log X)$ time.[実装例(C++)](https://atcoder.jp/contests/abc440/submissions/72248536)
投稿日時:
最終更新: