SRM572 Div2 Medium NextOrPrev

問題

SRM 572 - TopCoder Wiki

文字列をstartからgoalに変換したい. 変換方法は各文字を一つ辞書順の大きい文字に,逆に小さい文字に変換し,それを繰り返す. 何回でもできるが,それぞれにnextCost, prevCostがかかる. ただし,変換の過程で同じ文字が重複して現れてはいけない. この時の変換の最小コストを求める問題.もし,変換できなければ-1を返す.

解答

公式よりもこの回答のほうが分かりやすいと思う.

  • 変換の際重複が出来るかどうかは,startの各文字のrank(辞書順で何番目か)とgoalのrankを比べ各文字のrankを一致するか判定すれば良い.もしrankが一致しなければnext, prevの操作の過程で文字が重複する場面が出てくる.
  • もし,rankが一致するなら辞書順の小さい方 or 大きい方から順番に変換していけば,問題なく変換できるので,順番を考えずに各文字のnext or prevのコストを計算しそれを足し合わせれば良い.
using namespace std;

class NextOrPrev
{
public:
  int getMinimum(int nextCost, int prevCost, string start, string goal)
    {
      int n = start.size();
      vector<int> rank_start = vector<int>(n, 0);
      vector<int> rank_goal = vector<int>(n, 0);
      for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++) {
          if (i == j) continue;
          if (start[i] > start[j]) rank_start[i]++;
          if (goal[i] > goal[j]) rank_goal[i]++;
        }
      }
      int res = 0;
      for (int i = 0; i < n; i++) {
        if (rank_start[i] != rank_goal[i]) return -1;
        if (start[i] < goal[i]) res += nextCost * (goal[i] - start[i]);
        else  res += prevCost * (start[i] - goal[i]);
      }
      return res;
    }
};