TopCoder SRM617 DIV1 HARD - FarStrings

Source

TopCoder SRM617 DIV1 HARD (800pt)
Problem Statement

問題概要

この問題では，文字列はすべてアルファベット小文字のみからなるとする．
$N$ 文字の文字列 $T$ が与えられる．
$k=1,2,\ldots,N$ に対して，$T$ との編集距離がちょうど $k$ の長さ $N$ の文字列の中で，辞書順最小のものを求める問題．
制約条件を満たす任意の入力に対して，編集距離がちょうど $k$ になる文字列が存在することは保証されている．
編集距離とは，$1$ ステップで文字を $1$ 文字挿入する，文字を $1$ 文字変更する，文字を $1$ 文字削除するのいずれかができるとして，片方の文字列から別の文字列に変換するための最小ステップ数．

解法

まず，$2$ つの文字列 $A, B$ 間の編集距離を求めるのは典型的なDPで可能．
$A$ の最初 $i$ 文字からなる文字列と，$B$ の最初 $j$ 文字からなる文字列の編集距離を記憶しながら計算すれば良い．
$T$ と編集距離 $k$ で辞書順最小の文字列を各 $k$ について $1$ つずつ求めていけば良い．
辞書順最小のものを求めるために，$1$ 文字ずつ確定させていく．
つまり，最初が $\verb|a|$ から始まるような編集距離 $k$ の文字列が存在するかどうかをチェックして，
存在しなければ，$\verb|b|$ から始まるようなものを調べていき，
存在するなら，$\verb|a|$ を確定して，$\verb|aa|$ から始まるようなものが存在するかチェックしにかかる．
存在するかチェックするには，決めた最初の部分以外をワイルドカードとでも思っておいて，DPで編集距離の最小値と最大値を求める．
最小値を求める場合は，ワイルドカードは任意の文字と等しいと思って良く，最大値を求める場合は，ワイルドカードは任意の文字と異なると思えば良い．
（実際に，$N \leq 25$ より，$T$ には含まれないアルファベットが少なくても $1$ 文字存在し，ワイルドカードをそれに置き換えれば，そのような最大値を達成することができる）
最小値と最大値の間は，適当に，ワイルドカードを部分的に $T$ の文字と等しいと思えば，調整可能なので，$k$ がその最小値と最大値の間にあるかどうかをチェックすれば良い．

C++によるスパゲッティなソースコード

// #includeなどは略しています
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define INF 1000000000

int mn[100][100];
int mx[100][100];

int isValid(const char a[], const char b[], int n, int dist){
  int i, j, k;

  rep(i,n+1) rep(j,n+1) mn[i][j] = mx[i][j] = INF;
  rep(i,n+1) mn[i][0] = mn[0][i] = mx[i][0] = mx[0][i] = i;

  rep(i,n) rep(j,n){
    if(a[i]==b[j]){
      mn[i+1][j+1] = min(mn[i+1][j+1], mn[i][j]);
      mx[i+1][j+1] = min(mx[i+1][j+1], mx[i][j]);
    }
    if(b[j]=='*'){
      mn[i+1][j+1] = min(mn[i+1][j+1], mn[i][j]);
    }
    mn[i+1][j+1] = min(mn[i+1][j+1], mn[i+1][j] + 1);
    mn[i+1][j+1] = min(mn[i+1][j+1], mn[i][j+1] + 1);
    mn[i+1][j+1] = min(mn[i+1][j+1], mn[i][j] + 1);
    mx[i+1][j+1] = min(mx[i+1][j+1], mx[i+1][j] + 1);
    mx[i+1][j+1] = min(mx[i+1][j+1], mx[i][j+1] + 1);
    mx[i+1][j+1] = min(mx[i+1][j+1], mx[i][j] + 1);
  }

  if(mn[n][n] <= dist && dist <= mx[n][n]) return 1;
  return 0;
}

string solve(string t, int dist){
  int i, j, k, n;
  char res[1000];

  n = t.size();
  rep(i,n) res[i] = '*';

  rep(i,n){
    REP(j,'a','z'+1){
      res[i] = j;
      if(isValid(t.c_str(),res,n,dist)) break;
    }
  }
  
  res[n] = '\0';
  return (string)res;
}

class FarStrings {
public:
vector <string> find(string t) {
  int i, n;
  vector<string> res;
  string tmp;

  n = t.size();
  rep(i,n){
    tmp = solve(t, i+1);
    res.push_back(tmp);
  }

  return res;
}

}

Current time: 2024年04月19日22時26分21秒
Last modified: 2014年04月22日13時17分48秒 (by laycrs)
Tags: Competitive_Programming TopCoder Single_Round_Match SRM617 SRM_Div1_Hard
トップページに戻る

Logged in as: unknown user (not login)

ログイン：