\(k\) 色を混ぜた後の拡張 RGB 値、鮮やかさはそれぞれ

\[ (R, G, B) = \left( \frac{\sum{r_i}}{k}, \frac{\sum{g_i}}{k}, \frac{\sum{b_i}}{k} \right), \]

\[ \begin{aligned} &\frac{(R - \mu)^2 + (G - \mu)^2 + (B - \mu)^2}{3} \\ =& \frac{(2R - G - B)^2 + (-R + 2G - B)^2 + (-R - G + 2B)^2}{27} \\ =& \frac{1}{27} \times \frac{1}{2} \left( (3R - 3B)^2 + (\sqrt{3}(-R + 2G - B))^2 \right) \\ =& \frac{1}{54 k^2} \left( \left(\sum{(3r_i - 3b_i)} \right)^2 + \left(\sum{\sqrt{3}(-r_i + 2g_i - b_i)} \right)^2 \right) \end{aligned} \]

と表せます。つまり、 \(2\) 次元ベクトル \((x_i, y_i) = (3 r_i - 3 b_i, \sqrt{3} (-r_i + 2 g_i - b_i))\) が \(N\) 組与えられる。この中から \(k\) 個を選ぶとき、ベクトル和 \((X, Y)\) のノルムの \(2\) 乗 \(X^2 + Y^2\) を最大化するには？、という問題が解ければよいです。

これは ABC139F - Engines の拡張ともみなせます。

単位ベクトル \((\cos{\theta}, \sin{\theta})\) を固定し、この方向にベクトル和を伸ばすことを考えます。これを実現するには、\((\cos{\theta}, \sin{\theta})\) との内積が大きいような \((x_i, y_i)\) を貪欲に選べばよいです。

そこで、\(\theta = 0 \to 2 \pi\) の順に、内積が大きいような \(i\) のランキングを更新していくことを考えると、このランキングは \(O(N^2)\) 回更新されます。(任意の \(2\) つのインデックス \(i, j\) に対し、\(i, j\) の上下関係が入れ替わるのはちょうど \(2\) 回であるため)

ランキングが更新されるたびに上位 \(k\) 個のベクトルを足し合わせていては \(\Omega(N^3)\) 時間かかりますが、更新された場所のみ変更することにすれば \(O(N^2 \log{N})\) 時間のアルゴリズムを構築できます。

実装の際は、ランキングの更新が同時に \(2\) か所以上起こるケースや誤差などに注意してください。