SRM568 DIV2 -Level2

<問題>
①N個の箱が与えられる。
②それぞれの箱には、赤と緑と青のボールが複数個入っている。
③このとき、それぞれの箱に1色のボールしか入らないようにしたいとき、最小のボールの移動回数を求めよ。

<解き方>
ひとつの箱に着目した時、一番多く入っている色をそのまま残して、
他の色を移動したらよいことがわかる。

ただしこのとき、ひとつの色がどの箱にも少ない個数であるときに
その色に移動させる箱が存在しなくなるため、例外のケースも存在する。
このままではNG.

では全探索で考えるとすると、最大で箱が50個のためO(3^50)でNG.

では上の考え方を少し応用させると、それぞれの色は少なくとも1回は選ばれることとなる。
これがわかると、各色が1回ずつ選ばれる場合の数は最大でも50^3でOK.

つまり答えは、それぞれの色が1回選ばれる場合でループを回して、それ以外の箱は貪欲方で最大の個数の色を残してあげればよい。

(例外処理)
最後に例外として、今回は個数が最小で1個なのでこのままでOK.
最小で0個だと、選ばれない場合の数は削除しないといけないので注意。
最大の数も今回は50×10^6=5×10^7なのでint型でOK.

<コード>
class BallsSeparating {

public: int minOperations(vector<int> red, vector<int> green, vector<int> blue) {
int ans=1000000000;
int n=red.size();

FORE(i,0,n){
FORE(j,0,n){
if(i==j)continue;
FORE(k,0,n){
if(j==k || k==i)continue;
int cost=0;
FORE(x,0,n){
if(x==i)cost+=(green[x]+blue[x]);
else if(x==j)cost+=(red[x]+blue[x]);
else if(x==k)cost+=(red[x]+green[x]);
else cost+=(red[x]+green[x]+blue[x]-max(red[x],max(green[x],blue[x])));
}
ans=min(ans,cost);
}
}
}
return ans==1000000000? -1:ans ;
}

};

このエントリーをはてなブックマークに追加