結果

問題 No.874 正規表現間距離
ユーザー LayCurseLayCurse
提出日時 2019-08-30 21:43:41
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 54 ms / 2,000 ms
コード長 3,886 bytes
コンパイル時間 2,558 ms
コンパイル使用メモリ 213,300 KB
実行使用メモリ 19,524 KB
最終ジャッジ日時 2024-11-21 22:26:32
合計ジャッジ時間 4,515 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,820 KB
testcase_01 AC 2 ms
6,816 KB
testcase_02 AC 2 ms
6,820 KB
testcase_03 AC 2 ms
6,816 KB
testcase_04 AC 2 ms
6,820 KB
testcase_05 AC 2 ms
6,820 KB
testcase_06 AC 2 ms
6,816 KB
testcase_07 AC 2 ms
6,820 KB
testcase_08 AC 2 ms
6,820 KB
testcase_09 AC 2 ms
6,816 KB
testcase_10 AC 2 ms
6,820 KB
testcase_11 AC 2 ms
6,816 KB
testcase_12 AC 2 ms
6,820 KB
testcase_13 AC 2 ms
6,816 KB
testcase_14 AC 2 ms
6,816 KB
testcase_15 AC 2 ms
6,820 KB
testcase_16 AC 8 ms
8,460 KB
testcase_17 AC 9 ms
7,276 KB
testcase_18 AC 2 ms
6,816 KB
testcase_19 AC 2 ms
6,816 KB
testcase_20 AC 2 ms
6,816 KB
testcase_21 AC 2 ms
6,820 KB
testcase_22 AC 2 ms
6,820 KB
testcase_23 AC 2 ms
6,820 KB
testcase_24 AC 2 ms
6,820 KB
testcase_25 AC 25 ms
13,396 KB
testcase_26 AC 23 ms
12,872 KB
testcase_27 AC 52 ms
19,432 KB
testcase_28 AC 46 ms
17,256 KB
testcase_29 AC 54 ms
19,524 KB
testcase_30 AC 54 ms
19,460 KB
testcase_31 AC 54 ms
18,056 KB
testcase_32 AC 54 ms
18,104 KB
testcase_33 AC 2 ms
6,816 KB
testcase_34 AC 2 ms
6,816 KB
testcase_35 AC 3 ms
6,816 KB
testcase_36 AC 18 ms
11,688 KB
testcase_37 AC 17 ms
11,080 KB
testcase_38 AC 2 ms
6,824 KB
testcase_39 AC 2 ms
6,820 KB
testcase_40 AC 2 ms
6,820 KB
testcase_41 AC 2 ms
6,820 KB
権限があれば一括ダウンロードができます

ソースコード

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++){
    if(i+1 < As && (A[i+1] == '?' || A[i+1] == '*')){
      A[k++] = A[i];
      if(A[i+1] == '*'){
        Ar[k-1] = 1;
      }
      if(A[i+1] == '?'){
        Ar[k-1] = 2;
      }
      i++;
      continue;
    }
    A[k++] = A[i];
  }
  As = k;
  k = 0;
  for(i=0;i<(Bs);i++){
    if(i+1 < Bs && (B[i+1] == '?' || B[i+1] == '*')){
      B[k++] = B[i];
      if(B[i+1] == '*'){
        Br[k-1] = 1;
      }
      if(B[i+1] == '?'){
        Br[k-1] = 2;
      }
      i++;
      continue;
    }
    B[k++] = B[i];
  }
  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){
//     if(i+1 < As && (A[i+1] == '?' || A[i+1] == '*')){
//       A[k++] = A[i];
//       if(A[i+1] == '*') Ar[k-1] = 1;
//       if(A[i+1] == '?') Ar[k-1] = 2;
//       i++;
//       continue;
//     }
//     A[k++] = A[i];
//   }
//   As = k;
//   
//   k = 0;
//   rep(i,Bs){
//     if(i+1 < Bs && (B[i+1] == '?' || B[i+1] == '*')){
//       B[k++] = B[i];
//       if(B[i+1] == '*') Br[k-1] = 1;
//       if(B[i+1] == '?') Br[k-1] = 2;
//       i++;
//       continue;
//     }
//     B[k++] = B[i];
//   }
//   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