るくすの日記 ~ Out_Of_Range ~

主にプログラミング関係

SRM 539 Div2

250: PlatypusPaternity

変なバグを出して時間がかかってしまった。

class PlatypusPaternity {
public:
  int Can(string fm,string ms,string group){
    int ret = 0;
    rep(i,group.size()){
      if(group[i] == 'Y' && fm[i] == 'Y' && ms[i] =='Y') ret++;
      if(group[i] == 'Y' && (fm[i] == 'N' || ms[i] =='N')) return 0;
    }
    return ret + 2;
  }
  int maxFamily(vector <string> fC, vector <string> mC, vector <string> sG) {
    int res = 0;
    rep(f,fC.size())
      rep(m,mC.size())
	rep(s,sG.size())
	  res = max(res,Can(fC[f],mC[m],sG[s]));
    return res;
  }
};



500: Over9000Rocks

選んだ箱の下限の合計と上限の合計が、それらの箱で表現できる岩の数の区間端になる。

int N;
vector<int>lB,uB;
class Over9000Rocks {
public:

  int countPossibilities(vector <int> lowerBound, vector <int> upperBound) {
    N = lowerBound.size();
    lB = lowerBound; uB = upperBound;
    vector<pair<int,int> >cand;
    for(int i = 0; i < (1 << N);i++){
      int lb = 0 ,ub = 0;
      for(int j = 0; j < N; j++)
	if((i >> j) & 1)
	  lb += lB[j],ub += uB[j];
      if(lb > 9000 || ub > 9000)
	cand.pb(mp(lb,ub));
    }
    if(cand.empty()) return 0;
    sort(all(cand));
    vector<pair<int,int> > res;
    res.pb(cand[0]);
    for(int i = 1; i < cand.size(); i++){
      pair<int,int> tmp = res[res.size() - 1];
      if(tmp.first <= cand[i].first && cand[i].first <= tmp.second)
	res[res.size() - 1].second = max(res[res.size() - 1].second,cand[i].second);
      else res.pb(cand[i]);
    }
    int result = 0;
    rep(i,res.size())
      result += res[i].second - max(9000,res[i].first - 1);
    return result;
  }
};