SRM 597 Div2 Medium LittleElephantAndString

問題

SRM 597 - TopCoder Wiki

ある文字列Aをある文字列Bに変換する. 変換方法は任意の位置の文字を一番左に持ってくる. 最小の変換コストを答える問題. もし変換不可能であれば-1を返す.

解答

  • 操作の順番を考えるとややこしいので,操作の話を一旦脇において.B[n-1]の文字を合わせるコストを考える.
  • 総方法を考えるとAの後方B[n-1]が現れるまでの文字全てを移動させなければならない.
  • 次にB[n-2]をあわせるコストを考える.もしAの後方でまだ移動していない文字があるならば,移動した文字よりも先にこの中からB[n-2]と同じ文字を選ばなくてはいけない.
  • 同様にしてBの後方から合わせていく.
  • そうすると,残りはAで移動した文字とBの残りを合わせることになる.
  • Aに移動する順番は考えなかった.(あくまで移動するべき文字を選んだだけ)
  • この移動する文字の順番は,その前の処理に全く影響しないため,移動する順番は都合の良い様に解釈して良い.
  • もし,移動した文字の集合と,Bの残りの文字集合が一致すれば,AからBに変換でき,その最小コストはAの移動した文字数になる.

変換できるかの判定にコード数かかったが,ABをソートして比較すればそれだけで済むんだった...

class LittleElephantAndString
{
public:
  int getNumber(string A, string B)
    {
      int n = A.size();
      int i, j;
      // string free = "";
      vector<char> free;
      for (i = n-1, j = n-1; i >= 0 && j >= 0;){
        if (B[i] == A[j]) {
          j--;
          i--;
        }else {
          // cout << "A[" << j << "]=" << A[j] << endl;
          free.push_back(A[j]);
          j--;
        }
      }
      // cout << free.size() << endl;
      int res = free.size();
      for(; i >= 0; i--){
        bool found = false;
        for (j = 0; j < free.size(); j++){
          if (B[i] == free[j]){
            free.erase(free.begin() + j);
            found = true;
            break;
          }
        }
        if (!found) return -1;
      }
      return res;
    }
};