NOMURA プログラミングコンテスト 2021 B - RGB Matching (500)
RGBの犬がそれぞれ偶数匹なら同じ色だけで組み合わせられるので答えは0
そうでない場合でも一色は偶数匹
全部奇数なら総数も奇数になるため
以下RGを奇数匹、Bを偶数匹とする
RGの余りを組み合わせるパターン
R全てに対してそれぞれGの中でもっとも差が自身と小さいものを二分探索で見つける
今までの答えの最小値より小さかったら更新する
RB,GBの組み合わせを作るパターン
R全てに対してそれぞれBの中でもっとも差が自身と小さいものを二分探索で見つける
G全てに対してそれぞれBの中でもっとも差が自身と小さいものを二分探索で見つける
これらの最小値の和がより小さかったら更新する
RB,GBの組み合わせでどちらも同じBの値を洗濯した場合でもRGの余りを組み合わせるパターンより良くはならない
位置関係がR,B,Gの順なら$ (B-R)+(G-B)=G-Rで同じ
間に無いなら明らかに悪い
ソートと二分探索がボトルネックで$ \mathcal{O}(N \log N)