◆Solution 1: Using Binary Search

Since \(\left|\frac{B_i}{M} - \frac{A_i}{N}\right| = \frac{1}{NM}\left|NB_i - MA_i\right|\), let us think of minimizing \(\max_i|NB_i - MA_i|\) instead.

Examining the Decision Problem

Let us use binary search to find the minimum possible value of \(\max_i|NB_i - MA_i|\). For that, we want to solve the decision problem of whether there is an integer sequence \(B\) satisfying the following for a constant \(x\):

• \(\max_i|NB_i - MA_i| \leq x\);
• \(B_i\) is an non-negative integer satisfying \(\sum B_i = M\).

\(\max_i|NB_i - MA_i|\leq x\) is equivalent to \(\forall i, |NB_i - MA_i|\leq x\). Here the condition is independent for each \(i\), which is the good point of converting the problem into a decision one. Moreover, from the following:

\[|NB_i-MA_i|\leq x \iff MA_i-x\leq NB_i\leq MA_i+x\iff \left\lceil \frac{MA_i-x}{N}\right\rceil\leq B_i\leq \left\lfloor\frac{MA_i+x}{N}\right\rfloor\]

after setting the values \(L_i, R_i\) properly, the problem is reduced to determine whether there is an integer sequence \(B\) satisfying the following:

• \(L_i\leq B_i\leq R_i\)
• \(B_i\) is an non-negative integer satisfying \(\sum B_i = M\).

Solution of the Decision Problem

For \(B\) to exist, it is necessary that \(\sum L_i\leq M\leq \sum R_i\). On the other hand, under this necessary condition, we can prove the existence of a sequence \(B\) satisfying the condition, which can be actually built as follows:

• First, set the sequence \(B_i\) to \(B_i = L_i\).
• For each \(i = 1, 2, \ldots, K\) in this order, do the following:
  • make \(B_i\) as large as possible while making sure that the sum of \(B\) is at most \(M\) and \(B_i\leq R_i\).

Let us confirm it. First, in the above steps, we can easily see that:

• \(L_i\leq B_i\leq R_i\) always holds;
• the sum of \(B\) monotonically increases throughout the algorithm and does not exceed \(M\).

From the monotonicity, what remains is to show that it is never the case that the sum of \(B\) is always less than \(M\). If it is the case, each step of the algorithm chooses \(B_i = R_i\), leading to the final sequence of \(B = (R_1, \ldots, R_K)\). However, we have assumed that \(M\leq \sum R_i\), so this result contradicts the assumption of the sum of \(B\) always being less than \(M\).

Summary

We have seen that we can determine whether \(\max_i|NB_i - MA_i| \leq x\) can be realized by computing \(L_i, R_i\) and checking if \(\sum L_i \leq M\leq \sum R_i\) holds. Thus, we can solve the decision problem in \(O(K)\) time, and doing so in the binary search finds the minimum possible value of \(\max_i|NB_i - MA_i|\) in \(O(K\log NM)\) time.

The problem also asks to construct a sequence \(B\) that achieves the minimum value, which can also be done in \(O(K)\) time in the method described above. Therefore, we can solve the problem in \(O(K\log NM)\) time.

【Sample Implementation】 https://atcoder.jp/contests/arc118/submissions/22249436 (Python, \(O(K\log NM)\) time)

---

◆Solution 2: Greedy Strategy

By improving the above solution, we can also directly construct the solution.

The problem is easy if \(B_i\) does not have to be an integer; in that case, we should set \(B_i = \frac{MA_i}{N}\). From this, can we make the following conjecture?

• \(B_i\) in the optimal solution is the integer nearest to \(\frac{MA_i}{N}\) on either side.
• The optimal solution satisfies \(\max_i\left|B_i-\frac{MA_i}{N}\right| < 1\).

We will begin by proving them and narrow the range to be searched.

Narrowing the Solution Space

In the decision problem in Solution 1, let us set \(x = N - 1\). Remember that we can solve the problem as follows:

• let \(L_i = \left\lceil\frac{MA_i-N+1}{N}\right\rceil\), \(R_i = \left\lfloor\frac{MA_i+N-1}{N}\right\rfloor\);
• if \(\sum L_i\leq M\leq \sum R_i\), \(B\) exists.

We can prove that this condition \(\sum L_i\leq M\leq \sum R_i\) always holds. Actually, from \(L_i = \left\lfloor\frac{MA_i}{N}\right\rfloor\) and \(R_i = \left\lceil\frac{MA_i}{N}\right\rceil\), we can see that \(L_i\leq \frac{MA_i}{N}\leq R_i\). From this and \(\sum\frac{MA_i}{N} = M\), the condition always holds. This means that, to find the optimal \(B\), we only need to search it from the sequences satisfying \(L_i \leq B_i\leq R_i\). It follows from \(R_i < L_i + 2\) that \(B_i \in \{L_i, L_i + 1\}\): we have two choices for each \(B_i\) that need to be checked.

Rephrasing the Problem and Taking a Greedy Strategy

Now, let \(B_i = L_i + x_i\) and rephrase the problem into the choices of \(x_i \in \{0,1\}\). Since \(|NB_i - MA_i| = |N(L_i+x_i) - MA_i| = |Nx_i + (NL_i - MA_i)|\), let \(C_i = NL_i - MA_i\) and \(n = M - \sum L_i\) to reduce the problem into the following:

Given is a sequence \(C = (C_1, \ldots, C_K)\). Among the ways to choose \(n\) of the indices \(i\) and adding \(N\) to \(C_i\) for each chosen \(i\), find the one that minimizes \(\max |C_i|\).

If \(n\geq 1\), among the optimal solutions, there exists one that chooses the minimum \(C_i\). This is because if the minimum \(C_i\) is not chosen in some solution, we can change one of the choices to \(C_i\) without making \(\max|C_i|\) larger. By making a similar observation in the situation with the remaining \(K-1\) numbers and \(n-1\) choices, we can see that an optimal solution chooses the two smallest \(C_i\) if \(n\geq 2\). Continuing this way, we can see that the problem above can be solved with the following greedy algorithm:

• choose the \(n\) smallest elements \(C_i\) for adding \(N\).

Summary

We can solve the problem as follows:

• Let \(L_i = \left\lfloor\frac{MA_i}{N}\right\rfloor\), \(C_i = NL_i - MA_i\), \(n = M - \sum L_i\).
• Let \(B_i = L_i\). Choose the \(n\) smallest elements from \(C_i\) and add \(1\) to \(B_i\) for each chosen \(i\). The sequence \(B_i\) we have now is one of the optimal solution.

This can be done in \(O(K\log K)\) time with sorting, or in \(O(K)\) time with a linear time selection algorithm.

【Sample Implementation】 https://atcoder.jp/contests/arc118/submissions/22249102 (Python, \(O(K)\) time)