yukicoder No.1554 array_and_me - かんプリンの学習記録

問題概要
解説
提出プログラム
感想

問題概要

長さ ${N}$ の正整数列 ${A}$ が与えられる． ${P_i=\frac{A_i}{\sum_{i=1}^{N}A_i}}$ として ${\displaystyle\underset{z_1+z_2+\cdots z_N=K}{\max}\frac{K!}{z_1!z_2!\cdots z_N!}P_1^{z_1}P_2^{z_2}\cdots P_N^{z_N}}$ を求めよ．

${1\leq N,K\leq 10^5\\ 1\leq A_i\leq 10^3}$

解説

${\displaystyle\underset{z_1+z_2+\cdots z_N=K}{\max}\frac{K!}{z_1!z_2!\cdots z_N!}P_1^{z_1}P_2^{z_2}\cdots P_N^{z_N}\\ =\displaystyle\underset{z_1+z_2+\cdots z_N=K}{\max}K!\prod_{i=1}^{N}\frac{P_i^{z_i}}{z_i!}\\ =\displaystyle\underset{z_1+z_2+\cdots z_N=K}{\max}K!\prod_{i=1}^{N}\prod_{j=1}^{z_i}\frac{P_i}{j}}$
できるだけ大きな ${\displaystyle\frac{P_i}{j}}$ を使いたい． ${\displaystyle\frac{P_i}{j} > \frac{P_i}{j+1}}$ であるから，貪欲で大丈夫． ${\displaystyle\frac{P_i}{x}}$ と ${\displaystyle\frac{P_j}{y}}$ の比較は ${A_i y}$ と ${A_j x}$ を比較すればよい．もしくは，二分探索でも解ける．

基本的には，https://atcoder.jp/contests/joisc2008/tasks/joisc2008_fractionやhttps://yukicoder.me/problems/no/68やhttps://yukicoder.me/problems/no/210と同じ．

${1\leq k\leq K}$ を満たす全ての ${k}$ について求めよ，とかでも解けます．