◆解法 1：二分探索の利用

\(\left|\frac{B_i}{M} - \frac{A_i}{N}\right| = \frac{1}{NM}\left|NB_i - MA_i\right|\) なので、代わりに \(\max_i|NB_i - MA_i|\) の最小化問題を考えることにします。

判定問題の整理

二分探索により、可能な \(\max_i|NB_i - MA_i|\) の最小値を求めることを考えます。そのために、定数 \(x\) に対して、以下を満たす整数列 \(B\) が存在するかという判定問題を考えます。

• \(\max_i|NB_i - MA_i| \leq x\)
• \(B_i\) は非負整数で、\(\sum B_i = M\) を満たす

\(\max_i|NB_i - MA_i|\leq x\) は \(\forall i, |NB_i - MA_i|\leq x\) と同値で、\(i\) ごとに独立な条件に変わるのが判定問題に書き変えた利点です。さらに

\[|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\]

なので、\(L_i, R_i\) を適切に定めることで、次を満たす整数列 \(B\) の存在を判定する問題に帰着されます。

• \(L_i\leq B_i\leq R_i\)
• \(B_i\) は非負整数で、\(\sum B_i = M\) を満たす

判定問題の解法

\(B\) の存在には、\(\sum L_i\leq M\leq \sum R_i\) が必要です。逆にこの必要条件のもと、条件を満たす整数列 \(B\) の存在が証明できます。実際、次のアルゴリズムにより構築できます。

• まず、\(B_i = L_i\) により整数列 \(B_i\) を定める。
• \(i = 1, 2, \ldots, K\) の順に次を行う。
  • 数列 \(B\) の総和が \(M\) を超えない範囲、かつ \(B_i\leq R_i\) を満たす範囲の中で、可能な限り \(B_i\) を大きい値に変更する

このことを確かめましょう。まずこの手順において、

• 常に \(L_i\leq B_i\leq R_i\)
• 数列 \(B\) の総和は、アルゴリズムの進行について単調増加であり、また、\(M\) を超えることはない

が成り立つことが容易に分かります。単調増加性より、「常に数列 \(B\) の総和が \(M\) 未満」ということが起こりえないことを示せばよいです。もしこれが成り立ったとすると、アルゴリズムの各段階で \(B_i = R_i\) が選ばれることになり、最終的に \(B = (R_1, \ldots, R_K)\) という数列が得られます。ところが \(M\leq \sum R_i\) を仮定していたので、この結果は「常に \(B\) の総和が \(M\) 未満」という仮定に反しています。

解法まとめ

以上により、\(\max_i|NB_i - MA_i| \leq x\) が実現できるかという判定問題は、\(L_i, R_i\) を計算して、\(\sum L_i \leq M\leq \sum R_i\) が成り立つかを確認することで解けると分かりました。したがって、判定問題は、\(O(K)\) 時間で解けます。二分探索内で判定問題を解くことで、\(\max_i|NB_i - MA_i|\) の最小値は \(O(K\log NM)\) 時間で計算することができます。

本問題では、最小値を達成する場合の数列 \(B\) の構築が要求されています。この構築も、上で説明した方法により \(O(K)\) 時間で行うことができます。以上により、本問題は \(O(K\log NM)\) 時間で解くことができます。

【解答例】 https://atcoder.jp/contests/arc118/submissions/22249436 （Python, \(O(K\log NM)\) 時間）

---

◆解法2：貪欲法による構築

解法 1 を洗練させることで、貪欲法により直接解を構築することもできます。

本問題は、\(B_i\) の整数性を要求しなければ簡単で、その場合には \(B_i = \frac{MA_i}{N}\) と定めることになります。このことから、

• 最適解を与える \(B_i\) は、\(\frac{MA_i}{N}\) から見て小さい側・大きい側のどちらかに最も近い整数である。
• 最適解において、\(\max_i\left|B_i-\frac{MA_i}{N}\right| < 1\) が成り立つ。

と予想できるのではないでしょうか？このことを証明して、最適解の探索範囲を絞り込むところから始めます。

最適解の絞り込み

解法 1 の判定問題において、\(x = N - 1\) としてみます。判定問題は、次のように解けるのでした。

• \(L_i = \left\lceil\frac{MA_i-N+1}{N}\right\rceil\), \(R_i = \left\lfloor\frac{MA_i+N-1}{N}\right\rfloor\) とする。
• \(\sum L_i\leq M\leq \sum R_i\) ならば、数列 \(B\) が存在する。

この条件 \(\sum L_i\leq M\leq \sum R_i\) は必ず成り立つことが証明できます。実際 \(L_i = \left\lfloor\frac{MA_i}{N}\right\rfloor\), \(R_i = \left\lceil\frac{MA_i}{N}\right\rceil\) より \(L_i\leq \frac{MA_i}{N}\leq R_i\) であることが分かるので、\(\sum\frac{MA_i}{N} = M\) であることから従います。また最適解 \(B\) としては、\(L_i \leq B_i\leq R_i\) を満たすものの中から探索すれば十分だということになります。\(R_i < L_i + 2\) なので、\(B_i \in \{L_i, L_i + 1\}\) が分かり、各 \(B_i\) としては \(2\) 通りの候補を調べればよいことが分かりました。

問題の言い換え・貪欲アルゴリズム

\(B_i = L_i + x_i\) として、\(x_i \in \{0,1\}\) を選ぶという問題に書き変えてみましょう。\(|NB_i - MA_i| = |N(L_i+x_i) - MA_i| = |Nx_i + (NL_i - MA_i)|\) なので、改めて \(C_i = NL_i - MA_i\) とおき、\(n = M - \sum L_i\) とおくことで、次の問題に帰着されます。

数列 \(C = (C_1, \ldots, C_K)\) が与えられる。「\(C_i\) をひとつ選び \(N\) を加える」という操作をちょうど \(n\) 個の \(i\) に対して行う方法のうち、\(\max |C_i|\) が最小になるものを答えよ。

\(n\geq 1\) であるとき、最適解のうち、最小の \(C_i\) に \(N\) を加えるという操作を行うものが存在します。\(C_i\) に加算を行わない操作に対して、ひとつの加算対象を \(C_i\) に変更しても　\(\max|C_i|\) が大きくなることはないためです。残り \(K-1\) 数 \(n-1\) 回の状況で同様に考えることで、\(n\geq 2\) ならば \(C_i\) のうち小さい方から \(2\) つには \(N\) を加えるとしてよいことが分かります。同様に考えると、上述の問題は次の貪欲アルゴリズムにより解くことができます：

• \(C_i\) のうち小さいものから \(n\) 個を選び、\(N\) を加える。

解法まとめ

本問題は、次の手順により解くことができます。

• \(L_i = \left\lfloor\frac{MA_i}{N}\right\rfloor\), \(C_i = NL_i - MA_i\), \(n = M - \sum L_i\) とおく。
• \(B_i = L_i \) とする。\(C_i\) のうち小さいものから \(n\) 個を選び、そのような \(i\) に対して \(B_i\) に \(1\) を加える。こうして得られた \(B_i\) が求める最適解のひとつである。

ソートを利用して \(O(K\log K)\) 時間で解いたり、線形時間の選択アルゴリズムを用いて \(O(K)\) 時間で解くことができます。

【解答例】 https://atcoder.jp/contests/arc118/submissions/22249102 （Python, \(O(K)\) 時間）