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にしては易しい?