SRM 557 Div2 Medium IncubatorEasy

問題

あなたは女の子を魔法少女に変える能力を持っている. 今N人の女の子がいて,i番目の女の子がj番目の女の子を愛している時love[i][j]=Yと表現する. 魔法少女iはlove[i][j]=Yとなる少女jをあなたから守ることが出来る(少女jを魔法少女に変えることが出来ない). 守られている少女iもlove[i][j]=Yとなる少女jを同様にあなたから守ることが出来る.

守られていない魔法少女の最大数を答えよ.

解答

魔法少女に変える作業を全探索してみたが,時間切れになってしまった. 10!かかるからだめだったか

回答を見て,魔法少女に変える少女のパターンを全探索すればよいと気づいた.

魔法少女iが好きなjが好きなk・・・など,好きな少女同士のリンクが連なる時の処理は,予め処女iから辿れる少女全てを事前に計算しておけばよかった.

以下は時間切れになるコード

class IncubatorEasy
{
public:
  int maxMagicalGirls(vector <string> love)
    {
      int n = love.size();
      int i, j;
      vector<int> idx;
      vector<vector<bool> > loves(n, vector<bool>(n, false));
      for(i = 0; i < n; i++){
        for(j = 0; j < n; j++) loves[i][j] = love[i][j] == 'Y';
      }
      for(i = 0; i < n; i++) idx.push_back(i);
      int res = 0;
        vector<bool> isProtected(n, false);
        vector<bool> isMagical(n, false);
      do{
        vector<bool> isProtected(n, false);
        vector<bool> isMagical(n, false);
        int cur = 0;
        int cur_max = 0;
        for(i = 0; i < n; i++){
          if (!isMagical[idx[i]] && !isProtected[idx[i]]){
            isMagical[idx[i]] = true;
            cur++;
            vector<int> new_protected;
            for(j = 0; j < n; j++){
              if (!isProtected[j] && loves[idx[i]][j]){
                new_protected.push_back(j);
                isProtected[j] = true;
                if (isMagical[j]) cur--;
              }
            }
            while(!new_protected.empty()){
              int girl = new_protected.back();
              new_protected.pop_back();
              for(j = 0; j < n; j++) {
                if (loves[girl][j] && !isProtected[j]){
                  new_protected.push_back(j);
                  isProtected[j] = true;
                  if (isMagical[j]) cur--;
                }
              }
            }
          }
          cur_max = max(cur_max, cur);
        }
        res = max(res, cur_max);
        if (res == n) return res;
      }while(next_permutation(idx.begin(), idx.end()));
      return res;
    }
};