SRM387 Div2 600

問題

いくつかの箱にさまざまな種類の色のビーダマが適当に入っている。
それを以下の条件を満たすように入れなおす。

• 1つの箱だけは「ジョーカーボックス」として、違う色のビーダマが存在してよい
• その他の箱は、ただ1種類の色のビーダマだけが入っていなければならない
• すべての同じ色のビーダマは、ジョーカーボックスを除いて、同じ箱にはいっていなければならない。

一回の移動では、1つの箱のいくつかのビーダマをまとめて別な箱に移せる(同じ色でなくてよい)。
上記を満たすような最小な入れ代え数を返す。

考え方

一つの箱をジョーカーボックスとして取り除いた残りの箱について考える。
基本的には、他の箱に移す場合、ジョーカーボックスに移せばよいのがわかる。
なので、複数の色が入っている箱はジョーカーボックスに移す。
1種類しか入っていない箱について注目すると、3番目の条件より同じ色のビーダマは1つの箱にまとめて置かれなければいけないので、そのような箱は1つ残してすべてジョーカーボックス(またはその1つの箱)に移す。
この移した回数の最小回数を保持して、ジョーカーボックスを選んだそれぞれの場合について計算すればいい。