AtCoder Beginner Contest 231
Panasonic Programming Contest 2021(AtCoder Beginner Contest 231)
E. Minimal payments
Easy digit DP practice.
G. Balls in Boxes
Consider the Multivariable PGF of this problem:
\[ f=\frac{1}{n^k}\prod x_i^{A_i}\left(\sum x_i\right)^k \]
The term of the score, which is \(\prod _{i=1}^NB_i\), immediately implies the answer to the problem.
\[ E(score)=\left[ \frac{\partial^N f}{\partial x_1\partial x_2\dots\partial x_N} \right ]_{x_i=1} \]
We can notice that
\[ \frac{\partial }{\partial x_i}x_i^{m_i}\prod_{j\not=i} x_j^{m_j} \left(\sum x_i\right)^k =m_ix_i^{m_i-1}\prod_{j\not=i} x_j^{m_j}\left(\sum x_i\right)^k+kx_i^{m_i}\prod_{j\not=i} x_j^{m_j} \left(\sum x_i\right)^{k-1} \]
Let coef[n] be the coefficient of \(\prod x_i^{c_i}\left(\sum x_i\right)^n\),
we can easily process the partial derivative by an \(O(n^2)\) DP.
H. Minimum Coloring
The problem can be easily reduced to a weighted minimum edge cover problem on a bipartite graph.
Let's first choose the minimum cost at each vertices, and let it be \(C_u\).
Now we change the weight of each edge\((u, v, w)\) to \(w'=w-C_u-C_v\).
The answer should be \(\sum C_u-\) minimum cost matching of the resulting graph.
Since the new graph now have negative cost edges, we can solve the problem as follows: (from AtCoder editorial)
add a constant to make all weight positive, and subtract it accordingly on the minimum cost slope.
Alternatively, we may add an edge from S to T with capacity min(H,W) and cost BIG and find the minimum cost of flow min(H,W) to find the answer in the same way.