SRM422

「重さの合計が与えられた上限を超えない部分集合を全部返す」というアルゴリズムをさらっと書けなかったので終わってから頑張った。

void find_all_subset(
  const vector<size_t> &elems, const vector<int> &weight, 
  int weightLimit, vector<vector<size_t> > &result,
  int start=0, vector<size_t> already_member=vector<size_t>()){
  for(size_t i=start; i<elems.size(); i++){
    if(weight[elems[i]] <= weightLimit){
      result.push_back(already_member); // copy
      result.back().push_back(elems[i]);
      find_all_subset(
	elems, weight,
	weightLimit - weight[elems[i]], result,
	i + 1, result.back()); /* result.back() はコピーされる */
    }
  }
  

} 
int main(){
  vector<int> weight;
  weight.push_back(1);
  weight.push_back(2);
  weight.push_back(3);
  weight.push_back(4);
  vector<size_t> member;
  for(size_t i=0; i<4; i++){
    member.push_back(i);
  }
  vector<vector<size_t> > result;
  find_all_subset(member, weight, 6, result);
}

今回のDiv1のNormal問題は「体重の合計が上限を超えず、さらにお互いに信頼している人でチームを作り、ゴールにたどり着いたチームのうちの一人は戻ってこないと行けなくて、もっともかかる時間の少ないもの」というよくあるパズルの複雑バージョンを解く問題だった。船に乗れるのが2人までとか、オオカミと羊は一緒に乗せては行けないとか、ああいうパズル。

今回からBoostが使えなくなってとても悲しい。Boostを使えば済む内容を劣化版自作Boostで書くとか不毛すぎる。

とりあえずboost/assign.hppの劣化コピーを作った。

template<class T>
vector<T>& operator <<(vector<T> &xs, T x){
  xs.push_back(x);
  return xs;
} 

int main(){
  vector<int> weight;
  weight << 1 << 2 << 3 << 4;
  DP(weight);
}