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

SRM 644 Div2 Medium LostCharacter

問題

小文字と'?'からなる,文字列リストが与えられる. '?'は任意の文字に置き換えられ,文字列のpositionは全ての文字列の中での辞書順位と定義される. 与えられた文字列リストの'?'を任意の文字に置き換え,positionに変換する時, 辞書順が最小となるpositionリストを求める問題.

解答

  • positionリストの辞書順を最小にするには,各文字列のpositionを最小にすることで達成できる.
  • 各文字列について辞書順が一番小さくなるように'?'を置き換え,他の文字列を一番大きくなるようにするのが最適.
  • 全ての文字列でそのように変換し,positionを計算することで問題を解くことが出来る.
class LostCharacter
{
public:
  string replace(string & s, char c) {
    string new_str = "";
    for (int i = 0; i < s.size(); i++) {
      if (s[i] == '?') new_str += c;
      else new_str += s[i];
    }
    return new_str;
  }
  vector <int> getmins(vector <string> str)
    {
      int n = str.size();
      int i;
      vector<int> res;
      for (string s: str){
        vector<string> str2;
        string target = replace(s, 'a');
        for (string s2:str) {
          if (s == s2) str2.push_back(replace(s2, 'a'));
          else str2.push_back(replace(s2, 'z'));
        }
        sort(str2.begin(), str2.end());
        for (i = 0; i < n; i++) if (str2[i] == target) break;
        res.push_back(i);
      }
      return res;
    }
};