kmjp's blog

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

TopCoder SRM 644 Div2 Medium LostCharacter

SRM644に参加。
残念ながらUnratedだったね。
自分はEasyは速解き出来てたので、Medium解けなかったけどレート上がりそうだっただけに残念。
この回はなぜかサイトに問題情報がない。

問題

N個の文字列S[i]がある。
各文字列中、一部の文字列は不明'?'である。

これらの文字列群を辞書順ソートするとき、各文字は最少で何番目に来る可能性があるか答えよ。

解法

S[i]がソート後最小何個目に来るか求めるには、S[i]中の'?'をすべて'a'にし、そのほかの'?'を'z'にしてソートしてみればよい。

class LostCharacter {
	public:
	
	int getmin(int cur,vector <string> S) {
		int i,x,y,N=S.size();
		FOR(i,N) {
			FOR(x,S[i].size()) if(S[i][x]=='?') {
				if(i==cur) S[i][x]='a';
				else S[i][x]='z';
			}
		}
		string s=S[cur];
		sort(S.begin(),S.end());
		FOR(i,N) if(s==S[i]) return i;
	}
	
	vector <int> getmins(vector <string> str) {
		int i;
		vector<int> V;
		FOR(i,str.size()) V.push_back(getmin(i,str));
		return V;
	}
}

まとめ

Div2 Mediumにしては易しい?