ARC118B - Village of M People

考え方

\begin{aligned}
\Biggl|\frac{B_{i}}{M} - \frac{A_{i}}{N} \Biggr|
= \frac{1}{MN} | N B_{i} - M A_{i}|
\end{aligned}

であるから，$| N B_{i} - M A_{i}|$を最小化すれば良い．

そこで，はじめに

\begin{aligned}
B_{i} = \biggl\lfloor \frac{M A_{i}}{N} \biggr\rfloor
\end{aligned}

としておき，

\begin{aligned}
M - \sum_{i=1}^{K} \biggl\lfloor \frac{M A_{i}}{N} \biggr\rfloor
\end{aligned}

を適切に$B_{i}$に振り分けることを考える．

$B_{i}$が1増えるということは，$N B_{i} - M A_{i}$は$N$増えることになる．また，$| N B_{i} - M A_{i}|$を最小化することは，下図で各点をなるべく原点に近づけることである．

ARC118B

図から，原点から離れている点ほど$N$を加えたときに原点に近づいた点に移ることがわかる．よって，「$N B_{i} - M A_{i}$が小さいものから優先して$B_{i}$に1を加える」操作を行う．

そして，この操作だけで

\begin{aligned}
\sum_{i=1}^{K} B_{i}
= M
\end{aligned}

とすることができる．なぜなら，

\begin{aligned}
\biggl\lfloor \frac{M A_{i}}{N} \biggr\rfloor
\leq \frac{M A_{i}}{N}
\leq \biggl\lceil \frac{M A_{i}}{N} \biggr\rceil
\leq \biggl\lfloor \frac{M A_{i}}{N} \biggr\rfloor + 1
\end{aligned}

より

\begin{aligned}
\sum_{i=1}^{K} \biggl\lfloor \frac{M A_{i}}{N} \biggr\rfloor
\leq \sum_{i=1}^{K} \frac{M A_{i}}{N} = M
\leq \sum_{i=1}^{K} \biggl(\biggl\lfloor \frac{M A_{i}}{N} \biggr\rfloor + 1 \biggr)
\end{aligned}

となるからである．

回答例

K, N, M = map(int, input().split())
A = list(map(int, input().split()))

B = [M * a // N for a in A]
diff = [(N * b - M * a, i) for i, (a, b) in enumerate(zip(A, B))]
diff.sort()

res = M - sum(B)
for i in range(res):
  B[diff[i][1]] += 1
  
print(*B)