SRM306 D2H BlockDistance

TopCoder Statistics - Problem Statement

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.

$oldText$に対してある文字列を挿入する操作をして$newText$にしたい．最小で何回の挿入で出来るか．出来ない場合は$-1$を出力する．

topcoderの制約上?なのかもしれないけど$oldText$, $newText$は分割されてvectorで来るので，どうせ連結するなら最初からその文字列を渡せば良いのに，と思った．

$$ dp[i+1][j+1] := oldTextをi番目まででnewTextをj番目まで合わせる時の最小の挿入回数 $$

として動的計画法．文字列のindexを$1-indexed$にしたため，最終的に答える場所は$dp[|oldText|][|newText|]$．遷移は，$oldText[i]$と$newText[j]$が一致している時は何も挿入する必要がないので，そのまま$dp[i][j]$ $\to$ $dp[i+1][j+1]$．後はそこから何文字目まで合わせる挿入を行うかを探索して，例えば$k$文字目まで合わせるとすると$dp[i][j] + 1$ $\to$ $dp[i+1][j+1]$．これでは$oldText$の先頭に追加することは考えられるが，最後に挿入することが考えられていないので，番兵として$X$を末尾に追加して合わせるようにした．

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

#include <iostream>
#include <sstream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <queue>
#include <map>
#include <set>

#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define INF 1<<30
#define mp make_pair

using namespace std;
typedef long long ll;
typedef pair<int,int> P;

int dp[1005][1005];

class BlockDistance {

    public:

    int minDist(vector <string> oldText, vector <string> newText) {
      rep(i, 1005) rep(j, 1005) dp[i][j] = INF;

      string s = "", t = "";
      rep(i, oldText.size()) s += oldText[i];
      rep(i, newText.size()) t += newText[i];
      s += "X";
      t += "X";

      dp[0][0] = 0;

      rep(i, s.size()) {
          rep(j, t.size()) {
              if(s[i] == t[j]) {
                  dp[i+1][j+1] = min(dp[i+1][j+1], dp[i][j]);
              }

              REP(k, j+1, t.size()) {
                  dp[i][k] = min(dp[i][k], dp[i][j] + 1);
              }
          }
      }

      if(dp[s.size()][t.size()] == INF) return -1;
      return dp[s.size()][t.size()];
    }
};
Aug 25th, 2016
srm, topcoder, 動的計画法, 文字列