SRM567-DIV1-500.cpp

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cassert>

using namespace std;

typedef long long int int64;
typedef vector<int> VI;

#define REP(i,a,b) for (int i=int(a); i<int(b); ++i)

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

vector <string> S;
int N;
int cnt[50][26];
bool enemy[50];
bool solve(int s) {
	REP(i, 0, N) {
		enemy[i] = (i!=s);
	}
	REP(counter, 0, 26) {
		bool failed = true;
		REP(c, 0, 26) {
			bool cok = true;
			REP(i, 0, N) {
				if (!enemy[i]) continue;
				if (cnt[i][c]>cnt[s][c]) {
					cok = false;
					break;
				}
			}
			if (cok) {
				failed = false;
				REP(i, 0, N) {
					if (cnt[s][c]>cnt[i][c]) {
						enemy[i] = false;
					}
				}
			}
		}
		if (failed)
			return false;
		bool remaining = false;
		REP(i, 0, N)
			if (enemy[i])
				remaining = true;
		if (!remaining)
			return true;
	}
	return false;
}

vector <int> StringGame::getWinningStrings(vector <string> _S) {
	S=_S;
	N = S.size();
	
	REP(i, 0, N) REP(j, 0, 26) cnt[i][j] = 0;
	REP(i, 0, N) {
		string& s = S[i];
		REP(j, 0, s.size()) {
			int c = s[j] - 'a';
			cnt[i][c]++;
		}
	}
	
	VI ans;
	REP(i, 0, N) {
		if (solve(i)) {
			ans.push_back(i);
		}
	}
	return ans;
}