SRM 621 Div2 Medium NumbersChallenge

問題

SRM 621 - TopCoder Wiki

整数配列が与えられた時,A君は任意の数字を思い浮かべる,B君はA君が思い浮かんだ数字を与えられた整数配列の数字を抜き出し足し合わせることで作る. B君が作ることの出来ない最小の数を求める問題.

解答

入力シーケンスサイズが20なので220とおり考えても大丈夫. そうすると可能な数を全て列挙することができるので,後はソートして,先頭から順にチェックし,出来ない数を求める.

class NumbersChallenge
{
public:
  int MinNumber(vector <int> S)
    {
      int i, j;
      int n = S.size();
      set<int> possible;
      for (i = 0; i < (1 << n); i++){
        int create = 0;
        for (j = 0; j < n; j++) if ((i >> j) & 1){
            create += S[j];
          }
        possible.insert(create);
      }
      vector<int> plist(possible.begin(), possible.end());
      sort(plist.begin(), plist.end());
      
      for (i = 1; i < plist.size(); i++){
        // cout << "plist[" << i << "]=" << plist[i] << endl;
        if (plist[i-1] + 1 != plist[i] ){
          return plist[i-1] + 1;
        }
      }
      return plist.back()+1;
    }
};