ACM/ICPC 2011 Asia Regional - Daejeon

Problem C - Color Length

問題概要

N台の車の列とM台の車の列が与えられます。
これらの車は、'A'〜'Z'の色のどれかで塗られています。
N台の車の列とM台の車の列を順番を変えずに、マージした列Sを作ります。
文字列Sにおいて、以下の方法によって求めたコストの最小値を求めてください。

＜コストの計算法＞

• 文字列Sにおいて、「文字Cが存在する末尾index - 文字Cが存在する先頭index」を求める
• これを全ての文字の種類について求め、それらを合計した値がコスト

方針

動的計画法で考えます。

 dp[i][j] =
   1つ目の列のi文字目、
   2つ目の列のj文字目まで使ったときの、
   最小コスト

プログラム

int n, m;
string a, b;

int dp[5002][5002];
int alpha[128];
int aCnt[5002][128], bCnt[5002][128];

//文字列sの各アルファベットの数の累積和を求める
//t[i][j] = sのi文字目までで、jの文字がいくつあったか
//alpha[i] = iの文字が、2つの文字列を合わせていくつあったか
void countAlpha(const string &s, int t[5002][128]){
  int len = s.length();

  for(int i = 0; i < len; i++){
    alpha[s[i]]++;

    for(int j = 'A'; j <= 'Z'; j++){
      if(s[i] == j){
        t[i + 1][j]++;
      }
      t[i + 1][j] += t[i][j];
    }
  }
}

int getCost(int i, int j, char ch){
  int res = 0;

  //chが先頭文字列であるとき
  if(aCnt[i][ch] + bCnt[j][ch] == 1){
    res -= i + j;
  }
  //chが末尾文字列であるとき
  if(aCnt[i][ch] + bCnt[j][ch] == alpha[ch]){
    res += i + j;
  }

  return res;
}

void solve(){
  for(int i = 0; i <= n; i++){
    for(int j = 0; j <= m; j++){
      dp[i][j] = INT_MAX;
    }
  }

  dp[0][0] = 0;

  for(int i = 0; i <= n; i++){
    for(int j = 0; j <= m; j++){
      if(dp[i][j] == INT_MAX) continue;

      //1つ目の文字列を1文字進められる
      if(i + 1 <= n){
        dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + getCost(i + 1, j, a[i]));
      }
      //2つ目の文字列を1文字進められる
      if(j + 1 <= m){
        dp[i][j + 1] = min(dp[i][j + 1], dp[i][j] + getCost(i, j + 1, b[j]));
      }
    }
  }

  cout << dp[n][m] << endl;
}

int main(){
  int T;
  cin >> T;

  while(T--){
    cin >> a >> b;
    n = a.length();
    m = b.length();

    memset(alpha, 0, sizeof(alpha));
    memset(aCnt, 0, sizeof(aCnt));
    memset(bCnt, 0, sizeof(bCnt));
    countAlpha(a, aCnt);
    countAlpha(b, bCnt);

    solve();
  }
}