結果

問題 No.874 正規表現間距離
ユーザー LayCurseLayCurse
提出日時 2019-09-01 01:05:24
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 58 ms / 2,000 ms
コード長 3,656 bytes
コンパイル時間 2,903 ms
コンパイル使用メモリ 212,788 KB
最終ジャッジ日時 2025-01-07 16:15:11
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 38
権限があれば一括ダウンロードができます

ソースコード

diff # 

#pragma GCC optimize ("Ofast")
#include<bits/stdc++.h>
using namespace std;
inline void rd(char &c){
  int i;
  for(;;){
    i = getchar_unlocked();
    if(i!=' '&&i!='\n'&&i!='\r'&&i!='\t'&&i!=EOF){
      break;
    }
  }
  c = i;
}
inline int rd(char c[]){
  int i, sz=0;
  for(;;){
    i = getchar_unlocked();
    if(i!=' '&&i!='\n'&&i!='\r'&&i!='\t'&&i!=EOF){
      break;
    }
  }
  c[sz++] = i;
  for(;;){
    i = getchar_unlocked();
    if(i==' '||i=='\n'||i=='\r'||i=='\t'||i==EOF){
      break;
    }
    c[sz++] = i;
  }
  c[sz]='\0';
  return sz;
}
inline void wt_L(char a){
  putchar_unlocked(a);
}
inline void wt_L(int x){
  char f[10];
  int m=0, s=0;
  if(x<0){
    m=1;
    x=-x;
  }
  while(x){
    f[s++]=x%10;
    x/=10;
  }
  if(!s){
    f[s++]=0;
  }
  if(m){
    putchar_unlocked('-');
  }
  while(s--){
    putchar_unlocked(f[s]+'0');
  }
}
template<class S, class T> inline S chmin(S &a, T b){
  if(a>b){
    a=b;
  }
  return a;
}
char A[2002];
char B[2002];
int As;
int Bs;
int Ar[2002];
int Br[2002];
int dp[2002][2002];
int solve(int x, int y){
  int k, res=1073709056;
  if(dp[x][y] >= 0){
    return dp[x][y];
  }
  if(x-1 >= 0 && Ar[x-1]){
    chmin(res, solve(x-1, y));
  }
  if(y-1 >= 0 && Br[y-1]){
    chmin(res, solve(x, y-1));
  }
  if(x-1 >= 0){
    chmin(res, solve(x-1, y) + 1);
  }
  if(y-1 >= 0){
    chmin(res, solve(x, y-1) + 1);
  }
  if(x-1 >= 0 && y-1 >= 0){
    if(A[x-1] == B[y-1]){
      k =0;
    }
    else{
      k =1;
    }
    chmin(res, solve(x-1, y-1) + k);
    if(Ar[x-1]==1){
      chmin(res, solve(x, y-1) + k);
    }
    if(Br[y-1]==1){
      chmin(res, solve(x-1, y) + k);
    }
  }
  return dp[x][y] = res;
}
int main(){
  int i, k, res;
  As = rd(A);
  Bs = rd(B);
  k = 0;
  for(i=0;i<(As);i++){
    A[k++] = A[i];
    if(i+1 < As && A[i+1] == '*'){
      Ar[k-1] = 1;
      i++;
      continue;
    }
    if(i+1 < As && A[i+1] == '?'){
      Ar[k-1] = 2;
      i++;
      continue;
    }
  }
  As = k;
  k = 0;
  for(i=0;i<(Bs);i++){
    B[k++] = B[i];
    if(i+1 < Bs && B[i+1] == '*'){
      Br[k-1] = 1;
      i++;
      continue;
    }
    if(i+1 < Bs && B[i+1] == '?'){
      Br[k-1] = 2;
      i++;
      continue;
    }
  }
  Bs = k;
  for(i=0;i<(As+1);i++){
    int j;
    for(j=0;j<(Bs+1);j++){
      dp[i][j] = -1;
    }
  }
  dp[0][0] = 0;
  res = solve(As, Bs);
  wt_L(res);
  wt_L('\n');
  return 0;
}
// cLay varsion 20190830-1

// --- original code ---
// char A[2002], B[2002];
// int As, Bs, Ar[2002], Br[2002];
// 
// int dp[2002][2002];
// 
// int solve(int x, int y){
//   int k, res = int_inf;
// 
//   if(dp[x][y] >= 0) return dp[x][y];
// 
//   if(x-1 >= 0 && Ar[x-1]) res <?= solve(x-1, y);
//   if(y-1 >= 0 && Br[y-1]) res <?= solve(x, y-1);
// 
//   if(x-1 >= 0) res <?= solve(x-1, y) + 1;
//   if(y-1 >= 0) res <?= solve(x, y-1) + 1;
// 
//   if(x-1 >= 0 && y-1 >= 0){
//     k = if[A[x-1] == B[y-1], 0, 1];
//     res <?= solve(x-1, y-1) + k;
//     if(Ar[x-1]==1) res <?= solve(x, y-1) + k;
//     if(Br[y-1]==1) res <?= solve(x-1, y) + k;
//   }
// 
//   return dp[x][y] = res;
// }
// 
// {
//   int i, k, res;
//   rd(A@As, B@Bs);
//   
//   k = 0;
//   rep(i,As){
//     A[k++] = A[i];
//     if(i+1 < As && A[i+1] == '*') Ar[k-1] = 1, i++, continue;
//     if(i+1 < As && A[i+1] == '?') Ar[k-1] = 2, i++, continue;
//   }
//   As = k;
//   
//   k = 0;
//   rep(i,Bs){
//     B[k++] = B[i];
//     if(i+1 < Bs && B[i+1] == '*') Br[k-1] = 1, i++, continue;
//     if(i+1 < Bs && B[i+1] == '?') Br[k-1] = 2, i++, continue;
//   }
//   Bs = k;
//   
//   rep(i,As+1) rep(j,Bs+1) dp[i][j] = -1;
//   dp[0][0] = 0;
//   res = solve(As, Bs);
//   wt(res);
// }
0