SRM 567 Div1 Medium

500
文字数の多い文字から考える。難しさが easy と大差ない気がする。

class StringGame {
public:
  vector <int> getWinningStrings(vector <string> S)
  {
    vector<int> ret;

    const int N = S.size();

    map<char, int> cnt[N];
    for (int i = 0; i < N; ++i) {
      for (int j = 0; j < S[i].size(); ++j) {
        ++cnt[i][S[i][j]];
      }
    }

    for (int i = 0; i < N; ++i) {
      bool win[N];
      fill(win, win + N, false);
      win[i] = true;
      const int C = 'z' + 1;
      bool vis[C];
      fill(vis, vis + C, false);

      while (true) {
        char next = 0;
        for (char c = 'a'; c <= 'z'; ++c) {
          if (vis[(int)c]) continue;
          bool hata = true;
          for (int j = 0; j < N; ++j) {
            if (win[j]) continue;
            hata = hata && (cnt[i][c] >= cnt[j][c]);
          }
          if (hata) {
            next = c;
            vis[(int)next] = true;
            break;
          }
        }
        if (next) {
          for (int j = 0; j < N; ++j) {
            if (!win[j] && cnt[i][next] > cnt[j][next]) win[j] = true;
          }
        } else {
          break;
        }
      }
      if (count(win, win + N, false) == 0) ret.push_back(i);
    }
    return ret;
  }
};