TopCoder SRM 567 Div1 Medium StringGame

問題

文字列の集合Sが与えられる。
先手はこのうちひとつの文字列を選ぶ。これをxとする。
また、先手はアルファベットに好きな順に優先順位をつける。

後手は、Sのうちx以外の文字列を好きに並べ替える。
並べ替えたあと、xがSのなかで、他のどの文字列よりも辞書順で小さくなっていたら、
先手の勝ち、そうでなければ後手の勝ちとする。

Sが与えられたとき、両者が最善を尽くすとして、
先手がxとして選んだときに必勝になる文字列の番号を全て求めよ。

ただし、A, B二つの文字列を辞書順で比較するとは、
A, Bで初めて異なる文字が出てきたとき、それをa, bとする
a < bならばA < Bで、そうでないならB < Aである。

制約条件

Sの文字列の長さは全て同じで50以下
2≦Sの要素数≦50
Sはアルファベット小文字からなる

方針

アルファベットの優先順位を決めたとき、
それに対して先手の作れる最も辞書順で小さな文字列は、
優先順位の高いアルファベットから順番にできるだけ並べた文字列。

この文字列が、他の文字列にどうやっても勝てればよい。

文字iを使って引き分けか勝ちにできる条件は、
xに含まれる文字iの個数が、他の文字列に含まれる文字iの個数より小さくないこと。

ここから、勝ちか引き分けにできる文字の集合が定まる。
その文字の集合を使って、勝てる文字列に勝つ。

残りについて、使っていない文字列で、勝ちか引き分けにできる文字の集合を定め、
その文字の集合を使って、勝てる文字列に勝つ。

これを変化がなくなるまで繰り返し、全ての文字列に勝っているかを見ればよい。

ソースコード

int cnt[50][26];

class StringGame {
	public:
	vector <int> getWinningStrings(vector <string> S) {
		
		memset(cnt, 0, sizeof(cnt));
		
		int n = S.size();
		rep(i, n){
			sort(all(S[i]));
			rep(j, S[i].size()) cnt[i][S[i][j] - 'a']++;
		}
		vi ans;
		rep(i, n){
			bool win[50] = {};
			bool update = 1;
			
			while(update){
				update = 0;
				bool ok[26] = {};
				
				rep(j, 26) ok[j] = cnt[i][j] > 0;
				
				rep(j, n) if(!win[j]) rep(k, 26) if(cnt[i][k] < cnt[j][k]) ok[k] = 0;
				
				rep(j, 26) if(ok[j]){
					rep(k, n) if(!win[k] && cnt[i][j] > cnt[k][j]){
						win[k] = 1;
						update = 1;
					}
				}
			}
			rep(j, n) if(i != j && !win[j]) goto FAIL;
			ans.pb(i);
			FAIL:;
		}
		return ans;
	}
}