SRM 650 Div2 Medium TaroFillingAStringDiv2

問題

SRM 650 - TopCoder Wiki

A, B, ?からなる文字列が与えられる. ?をA, Bに置き換えてAAとBBの数を極力少なくしたい. 最小のAAとBBの数の和を答える問題.

解答

  • 問題の性質として?が連続する区間は?の連続をABAB・・・かBABA・・・のどちらかに置き換えるのが最適.
  • ?の連続の置き換えは他の?の連続に影響しない.
  • 各?の連続でABABかBABAの置き換えを両方行い,低いコストのみを採用して計算していく.

コーディングが少し面倒だった. 解説のコードはとてもシンプルで良い感じ.

using namespace std;

class TaroFillingAStringDiv2
{
public:
  int getNumber(string S)
    {
      int n = S.size();
      int res = 0;
      int i, j;
      char AB[2] = {'B', 'A'};
      for (i = 0; i < n;) {
        if (S[i] == '?') {
          char prev = i > 0?S[i-1]:'Z';
          for (j = i + 1; j < n && S[j]=='?';j++) ;
          char next = j < n? S[j] : 'Z';
          int len = j - i;
          int cost1 = (prev == 'A') + (AB[len%2] == next);
          int cost2 = (prev == 'B') + (AB[(len+1)%2] == next);
          res += min(cost1, cost2);
          i = j;
        } else {
          res += i > 0? S[i-1] == S[i]:0;
          i++;
        }
      }
      return res;
    }
};