TopCoder SRM 387 Div1 Easy MarblesRegroupingEasy
問題
n個の箱にそれぞれi種類目のマーブルがboxes[i][j]個入っている。
何度か操作を繰り返して、次の状態を満たすようにしたい。
- 一つのjoker boxを決める。
- joker box以外の箱は、空であるか一種類のマーブルしか入っていない。
- 一種類のマーブルは、joker box以外の箱のうち、二つ以上に入っていない。
操作:ある箱のマーブルを全て取り、別の箱に全て入れる。
制約条件
boxes[i][j]≦9
n≦50
方針
joker boxをn通り試す。
joker boxを決めた後は、
複数種類のマーブルが入っている箱があったら、その箱の中身は全てjoker boxに入れる。
その後で、残ったマーブルが別の箱に散らばっていたら、一つを残して全てjoker boxに入れる。
ようにすれば最短回数で条件を満たすことができる。
ソースコード
class MarblesRegroupingEasy { public: int minMoves(vector <string> boxes) { int n=boxes.size(), m=boxes[0].size(); int ans=inf; rep(jk,n){ vector<vi> num(n,vi(m)); rep(i,n)rep(j,m)num[i][j]=boxes[i][j]-'0'; int cnt=0; rep(i,n)if(i!=jk){ int c=0; rep(j,m)if(num[i][j])c++; if(c<2)continue; cnt++; rep(j,m)num[i][j]=0; } rep(i,m){ int c=0; rep(j,n)if(j!=jk&&num[j][i])c++; cnt+=max(0,c-1); } ans=min(ans,cnt); } return ans; } };