\(B \geq C\) であること、\(A\) は広義単調増加であることを仮定します。適宜スワップやソートを行ってください。

各箱について、追加されるビー玉の個数の種類は高々 \(4\) 種類です。\(B=C\) の場合も、大筋は変わりません。

• \(B+C\) 個
• \(B\) 個
• \(C\) 個 (\(B \neq C\) の場合)
• \(0\) 個 (追加されない)

また、ここで \(B \geq C\) より \(B+C > B \geq C > 0\) です。

\(B+C\) 個のビー玉が追加される箱を \(k\) 個としましょう。この時、\(B\) 個のビー玉が追加される箱は \(X-k\) 個、\(C\) 個のビー玉が追加される箱は \(Y-k\) 個、追加されない箱は \(N-X-Y+k\) 個です。

\(k\) を固定することを考えます。この時、最適解の \(1\) つに “最初の \(k\) 箱に \(B+C\) 個のビー玉を追加し、次の \(X-k\) 箱に \(B\) 個のビー玉を追加し、その次の \(Y-k\) 箱に \(C\) 個のビー玉を追加する” 場合があることを証明できます。

証明について

更に一般化した “長さの等しい整数列 \(L\) と \(M\) を並べ替えて、\(L_i+M_i\) の最大値 - 最小値を最小化する問題” を考えます。

\(a \leq b\) かつ \(c \leq d\) である \(4\) つの整数について、\((b+d)-(a+c) \geq |(a+d)-(b+c)|\) であることから、\(L\) を広義単調増加に、\(M\) を広義単調減少に並び替えるのが最適解の \(1\) つだと示せます。原理的には、ARC121 の D 問題 の公式解説と同じです。

よって、元の問題も証明することができました。

以降、この選び方を単に “最適な選び方” と呼ぶことにします。

\(k\) としてあり得る値は最大で \(\left \lfloor \frac{N}{2} \right \rfloor\) 個あるので、各 \(k\) に対して計算量 \(Θ(N)\) かけると一部テストケースで実行時間制限に間に合いません。ここから計算量を改善する方法は、大きく \(2\) つに分かれます。

まず、効率よく \(k\) を全探索する解法を説明します。

\(k\) を固定したとき、\(A\) の最大値もしくは最小値になる可能性がある要素は高々 \(8\) 個しか考える必要がありません。そのため、各 \(k\) に対して \(O(1)\) で答えを求めることができます。計算量は、最初の (仮定段階の) ソートがボトルネックとなり \(O(N \log N)\) です。提出コード (C++)
また、SparseTable や SegmentTree によって同じオーダーで解くことができます。提出コード (C++, ACL 使用)

もう \(1\) つの解法を説明します。

最適な選び方の構造をよく観察すると、どんな場合でも最初の \(X\) 個の箱に \(B\) 個のビー玉を追加していることがわかります。
よって、上の証明を利用すると次のような選び方で十分なことがわかります。

まず最初の \(X\) 個の箱に \(B\) 個のビー玉を追加してから、もう一度 \(A\) をソートして、最初の \(Y\) 個の箱に \(C\) 個のビー玉を追加する。

\(B \geq C\) を仮定しているから成り立つことに注意してください。 計算量は、こちらも最初の (仮定段階の) ソートがボトルネックとなり \(O(N \log N)\) です。提出コード (C++)