R, G,B の出現回数がいずれも偶数であった場合、答えは明らかに \(0\) です。以後、R, G が奇数個、B が偶数個存在することを仮定します(それ以外の場合もほぼ同様です)。

不満が正の整数になるのは、RG, GB, BR の組を作った場合に限られます。

最適解のうち、RG, GB, BR の組がいずれも高々 \(1\) つしかないものが存在することは明らかです。\(2\) つ以上存在する組があった場合、同色の \(2\) つの組に組み替えることで、不満の総和を現在の値以下の値にすることができます。

また、RG, GB, BR の組は合計で \(2\) つ以下であるような最適解が存在することも明らかです。どれも \(1\) つずつ存在した場合は RR, GG, BB の \(3\) つの組に組み替えることで、不満の総和を現在の値以下にすることができます。

以上のこと、R, G が奇数個、B が偶数個存在することから最適解は以下のどちらかの形をしていることがわかります。

• RG 型の組が \(1\) つあり、他は全て同色の組
• GB,BR 型の組が \(1\) つずつあり、他は全て同色の組

後者の場合に同じものを共有して使ってしまった場合も前者の場合より値が小さくなることはありません。よって、異なる \(2\) 色の組について不満の値としてありうる値の最小値を計算すればよいです。これはソートがボトルネックとなり、 \(O(N \log N)\) で実行可能で十分高速です。