読者です 読者をやめる 読者になる 読者になる

kmjp's blog

競技プログラミング参加記です

TopCoder SRM 567 Div1 Medium StringGame

SRM

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

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


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


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

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の割に簡単ではあったが、これは本番中に解ききりたかったな…

広告を非表示にする