筋トレ4日目: SRM568 Div1Easy "Balls Separating"

■時間
8:25〜8:45

■問題 SRM568 Div1 Easy "Balls Separating"
赤、青、緑のボールが最低一つずつ入った箱がn個ある。

箱から箱へ任意のボールを一つずつ移動させる時、

どの箱にも異なる色のボールが入っていない状態を作るために最小の移動数を返せ。

■試した解き方
まず赤、青、緑のボールそれぞれの受け入れ口が最低一箱ずつ必要なことに着目。
超単純に、赤の受け入れ口、青の受け入れ口、緑の受け入れ口を全パターン網羅し、
各パターンにおいて下記ボール割り振りを行う。
ボールの割り振りは、各箱において「一番多い数のボールだけを残す」のが最小移動数になる。
なので、各箱で最多色以外の和を積算していき、前記赤,青,緑の全パターンの中で最小の積算値を返す。
1st submitでsystem test通った。

public int minOperations(int[] red, int[] green, int[] blue) {

int n=red.length;

boolean hasRed=false, hasGreen=false, hasBlue=false;

for(int i=0;i<n;i++)

if(red[i]>0){

hasRed=true;

break;

}

for(int i=0;i<n;i++)

if(green[i]>0){

hasGreen=true;

break;

}

for(int i=0;i<n;i++)

if(blue[i]>0){

hasBlue=true;

break;

}

{

int numOK=(hasRed?1:0)+(hasGreen?1:0)+(hasBlue?1:0);

if(numOK>n)

return -1;

}

int minSum=Integer.MAX_VALUE;

//choose a red, green, and blue container

{

for(int ri=0;ri<n;ri++){

if(red[ri]>0 || !hasRed){

for(int gi=0;gi<n;gi++){

if(gi!=ri && (green[gi]>0 || !hasGreen)){

for(int bi=0;bi<n;bi++){

if(bi!=gi && bi!=ri && (blue[bi]>0 || !hasBlue)){

int sum=0;

for(int i=0;i<n;i++){

if(i==ri)

sum+=green[i]+blue[i];

else if(i==gi)

sum+=red[i]+blue[i];

else if(i==bi)

sum+=red[i]+green[i];

else{

sum+=Math.min(Math.min(red[i]+green[i], green[i]+blue[i]), red[i]+blue[i]);

}

}

if(sum<minSum)

minSum=sum;

}

}

}

}

}

}

}

return minSum;

}

■Editorial
同じ解き方。
DP使った解き方も書いてあった。

■反省

・問題文の読み飛ばしで、各箱に最低ひとつずつボールが入っていることに気づかず、無駄なコードが入った。今回はそれでも正しくかけたから良かったが、注意しよう。

・ちなみに、最初はGreedyに、赤、青、緑の最低受け入れ口を見つけてしまい、その後積算すればいいと思ってしまったのだがサンプル入力でエラーが出たおかげで間違いに気づいた。・最大の入力条件であるn=50を試さずsubmitしてしまった。たかだがO(n^4)のアルゴリズムなので大丈夫と思ったが、本番ならば絶対にこれはしてはいけない。

・DPでの解き方も練習しておきたい。

■筋トレ記録
勝率75% (3/4)