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: 2017年11月21日04時12分20秒
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)

ログイン: