SRM568Div2
Mid:
箱が何個かあって、i番目の箱には赤いボールがR[i]個、緑のボールがG[i]個、青いボールがB[i]個入っている。
それぞれの箱で、1色のボールのみ入っている状態にするために、必要なボールの移動回数を求める。
これも本番で解けなかったorz..
まず箱が2以下だったら不可能なので問答無用で-1を返す。
3以上の時は、先にRGBそれぞれ専用の箱を確定して、後は箱の中で一番数が多いボールを残すようにgreedy.
#include <vector> #include <algorithm> #include <iostream> using namespace std; class BallsSeparating { public: int minOperations(vector <int> R, vector <int> G, vector <int> B) { int res=1<<30; int N = R.size(); if(N<3)return -1; for(int r=0; r<N; ++r) { for(int g=0; g<N; ++g) { if(r==g)continue; for(int b=0; b<N; ++b) { if(r==b || g==b)continue; int m=0; m += G[r] + B[r]; m += R[g] + B[g]; m += R[b] + G[b]; for(int i=0;i<N; ++i) { if(i==r || i==g || i==b)continue; int sum = R[i] + G[i] + B[i]; int me = max(R[i], max(G[i],B[i])); m += sum - me; } res = min(res,m); } } } return res; } };
Hard:
手札をシャッフルして、一番上のカードが手札の中で一番小さい数だったらテーブルに置く。
じゃなかったらもう一回シャッフル。を手札がなくなるまで繰り返すときシャッフル回数の期待値を求める。
Hardにしては簡単すぎでは・・
#include <vector> #include <map> #include <iostream> using namespace std; #define rep(i,n) for(int i=0;i<n;++i) class ShuffleSort { public: double shuffle(vector <int> cards) { sort(cards.begin(),cards.end()); map<int,int> cnt; rep(i,cards.size()) cnt[cards[i]]++; double res=1; rep(i,cards.size()) res += double(cards.size()-i)/(cnt[cards[i]]--) - 1; return res; } };