TopCoder SRM 567 Div1 Medium StringGame

さてDiv1 Medium。
本番は方向性を間違えてWrong Answerになった問題。
http://community.topcoder.com/stat?c=problem_statement&pm=12378

いくつかの文字列が与えられる。１人目のプレイヤーが１つ文字列選んで、文字列内の文字を並べ替えたうえで、さらにa-zの文字の順番を入れ替える。
２人目のプレイヤーが残りの任意の文字列を選んで任意に並べ替えたときでも、１人目の選んだ文字が辞書順で前にくるなら勝ち。
各文字列について、１人目が選択したとき勝利できるかどうかを答える。

まず、各文字列中でa-zがそれぞれいくつあるかカウントする。
１人目のプレイヤーが文字列を選んだあと、a-zの文字のうち、その文字の数が残された他の文字列より多いか等しい文字を選ぶ、という処理を繰り返す。
そのような文字が選べなければ、１人目はその文字列では必ずしも勝てないと判定できる。
文字が選べた場合、文字数が同じもののみ「残された文字列」リストに残し、少ない物はリストから捨てる。
「残された文字列リスト」が空になるなら、１人目はその文字列で勝てる。

本番は単純に登場頻度が多い順に文字を選択して失敗してしまった。

class StringGame {
	int L;
	int num[60][26];
	vector<string> Ss;
	public:
	int ok(int cur) {
		int i,j;
		vector<int> cand,c2;
		int vis[26];
		
		ZERO(vis);
		FOR(i,Ss.size()) if(i!=cur) cand.push_back(i);
		
		while(!cand.empty()) {
			int can=-1;
			FOR(i,26) {
				if(vis[i] || num[cur][i]==0) continue;
				int ok=1;
				FOR(j,cand.size()) if(num[cur][i]<num[cand[j]][i]) ok=0;
				if(ok) {
					can=i;
					break;
				}
			}
			if(can<0) return 0;
			
			vis[can]=1;
			c2=cand;
			cand.clear();
			FOR(i,c2.size()) if(num[cur][can]==num[c2[i]][can]) cand.push_back(c2[i]);
		}
		return 1;
	}
	
	
	vector <int> getWinningStrings(vector <string> S) {
		int i,x,y;
		vector<int> res;
		Ss=S;
		L=S[0].size();
		res.clear();
		
		ZERO(num);
		FOR(x,S.size()) FOR(y,L) num[x][S[x][y]-'a']++;
		
		FOR(i,S.size()) if(ok(i)) res.push_back(i);
		return res;
	}
};

まとめ

意外と単純な問題。実装自体は簡単で、アルゴリズムにたどり着くまでは勝負。
500ptの割に簡単ではあったが、これは本番中に解ききりたかったな…