ARC121 B RGB Matching
体色が赤の頭数を$ r, 緑の頭数を$ g, 青の頭数を$ bとおく. $ r, g, bがすべて偶数の場合, 答えは明らかに$ 0である. よってそうでない場合, すなわち$ r, g, bのうちちょうど$ 1つが偶数の場合について考える. $ bが偶数であると仮定して考える(入力で$ rまたは$ gが偶数となるようなパターンが与えられた場合, 配列ごと交換すればよい).
不満の総和が最小となるパターンは以下の$ 2つある.
青の犬については青の犬同士で組み合わせ, 赤と緑の犬についてはそれぞれちょうど$ 1頭選び, その犬たちを組み合わせ, 残りは同じ色同士で組み合わせる
赤と緑の犬についてはそれぞれちょうど$ 1頭選び, 青の犬についてはちょうど$ 2頭選び, 一方の青の犬については赤の犬と, もう一方の青の犬については緑の犬と組み合わせ, 残りは同じ色同士で組み合わせる
最小に選ぶ方法は$ 2つのパターン両方とも二分探索を用いて求められる. 計算量は$ O(N \log N)となる.