SRM571Div2

Easy:
'o'の数を数える

#include <vector>
#include <algorithm>
#include <iostream>
#include <string>
using namespace std;
#define rep(i,n) for(int i=0;i<n;++i)

class FoxAndGame {
public:
  int countStars(vector <string> result) {
    int res=0;
    rep(i,result.size())
      res += (int)count(result[i].begin(),result[i].end(),'o');
    return res;
  }
};

Mid:
辞書順にソートする

#include <vector>
#include <algorithm>
#include <sstream>
#include <iostream>
#include <string>
using namespace std;
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}
#define rep(i,n) for(int i=0;i<n;++i)

class FoxAndMp3Easy {
public:
  vector <string> playList(int n) {
    vector <string> res;
    rep(i,n)res.push_back(toString(i+1) + ".mp3");
    sort(res.begin(),res.end());
    while(res.size()>50)res.pop_back();
    return res;
  }
};

Hard:
解けなかったので1位の人のを参考に
O(2^k)のdfsをする

#include <vector>
#include <algorithm>
#include <iostream>
#include <string>
using namespace std;
#define rep(i,n) for(int i=0;i<n;++i)

class MagicMoleculeEasy {
public:
  vector<pair<int,int> > G;
  vector<int> S;
  int k;

  int dfs(vector<pair<int,int> > g, long long mask){
    int cnt = 0;
    rep(i,60)if(mask>>i&1)cnt++;

    if(cnt > k)return -1;
    if(g.empty()){
      int sum=0;
      vector<int> score;
      rep(i,S.size())
        if(mask>>i&1)sum+=S[i]; 
        else score.push_back(S[i]);
      sort(score.rbegin(),score.rend());
      rep(i,k-cnt)sum+=score[i];
      return sum;
    }

    int a = g[0].first;
    int b = g[0].second;
    vector<pair<int,int> > g1,g2;
    rep(i,g.size()){
      if(g[i].first != a && g[i].second != a)g1.push_back(g[i]);
      if(g[i].first != b && g[i].second != b)g2.push_back(g[i]);
    }
    return max(dfs(g1,mask|(1LL<<a)), dfs(g2,mask|(1LL<<b)));
  }

  int maxMagicPower(vector <int> magicPower, vector <string> magicBond, int _k) {
    G.clear();
    S = magicPower;
    k = _k;
    int n = magicBond.size();
    rep(i,n)rep(j,n)if(magicBond[i][j]=='Y')G.push_back(make_pair(i,j));
    return dfs(G,0);
  }
};