SRM 591 Div2 Medium ConvertibleStrings

問題

SRM 591 - TopCoder Wiki

'A'から'I'までの文字で構成された文字列AとBについて,ある関数P(c)によって 各ポジションについてP(A[i]) == B[i]が成り立つ時,文字列AとBはconvertibleと呼ぶ. 今AとBの同じ位置の文字を消去できる. 文字列AとBがconvertibleになるように消去する時,最小の削除数を求める問題.

解答

実際にP(c)を決めて,コストを計算し,最小コストを返す. P(c)は9!通りで十分計算可能な値.

using namespace std;

class ConvertibleStrings
{
public:
  int leastRemovals(string A, string B)
    {
      int n = A.size();
      vector<int> p(9, 0);
      for(int i=  0; i < 9; i++) p[i] = i;
      int res = n;
      vector<int> a(n, 0);
      vector<int> b(n, 0);
      for(int i = 0; i < n; i++) {
        a[i] = A[i] - 'A';
        b[i] = B[i] - 'A';
      }
      do {
        int score = 0;
        for (int i = 0; i < n; i++){
          if (p[a[i]] != b[i]) {
            score++;
          }
        }
        res = min(res, score);
      } while (next_permutation(p.begin(), p.end()));
      return res;
    }
};