結果

問題 No.874 正規表現間距離
ユーザー はまやんはまやん
提出日時 2019-08-31 10:53:16
言語 C++17(1z)
(gcc 9.2.0)
結果
AC  
実行時間 44 ms
コード長 4,947 Byte
コンパイル時間 1,876 ms
使用メモリ 19,204 KB
最終ジャッジ日時 2020-01-11 09:05:12

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
corner1.txt AC 0 ms
3,232 KB
corner2.txt AC 0 ms
3,240 KB
corner3.txt AC 4 ms
3,468 KB
corner4.txt AC 0 ms
3,304 KB
corner5.txt AC 4 ms
3,376 KB
hand1.txt AC 0 ms
3,328 KB
hand2.txt AC 4 ms
3,360 KB
hand3.txt AC 4 ms
3,408 KB
hand4.txt AC 0 ms
3,328 KB
hand5.txt AC 0 ms
3,344 KB
hand6.txt AC 4 ms
3,452 KB
hand7.txt AC 4 ms
3,424 KB
hand8.txt AC 0 ms
3,472 KB
hand9.txt AC 4 ms
3,292 KB
hand10.txt AC 0 ms
3,460 KB
hand11.txt AC 0 ms
3,324 KB
hand12.txt AC 8 ms
6,652 KB
hand13.txt AC 4 ms
6,652 KB
hand14.txt AC 4 ms
3,428 KB
hand15.txt AC 0 ms
3,340 KB
hand16.txt AC 0 ms
3,404 KB
hand17.txt AC 4 ms
3,456 KB
hand18.txt AC 4 ms
3,516 KB
hand19.txt AC 0 ms
3,516 KB
hand20.txt AC 4 ms
3,352 KB
long1.txt AC 20 ms
11,232 KB
long2.txt AC 16 ms
11,232 KB
long3.txt AC 40 ms
19,100 KB
long4.txt AC 40 ms
16,856 KB
long5.txt AC 40 ms
19,164 KB
long6.txt AC 40 ms
19,204 KB
long7.txt AC 40 ms
17,660 KB
long8.txt AC 44 ms
17,852 KB
long9.txt AC 0 ms
3,344 KB
random1.txt AC 4 ms
3,396 KB
random2.txt AC 0 ms
3,696 KB
random3.txt AC 16 ms
10,640 KB
random4.txt AC 12 ms
10,464 KB
sample1.txt AC 4 ms
3,312 KB
sample2.txt AC 4 ms
3,468 KB
sample3.txt AC 0 ms
3,492 KB
sample4.txt AC 4 ms
3,504 KB
テストケース一括ダウンロード

ソースコード

diff #
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
//#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
template<class T>bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; }
//---------------------------------------------------------------------------------------------------
/*---------------------------------------------------------------------------------------------------
            ∧_∧
      ∧_∧  (´<_` )  Welcome to My Coding Space!
     ( ´_ゝ`) /  ⌒i     @hamayanhamayan
    /   \     | |
    /   / ̄ ̄ ̄ ̄/  |
  __(__ニつ/     _/ .| .|____
     \/____/ (u ⊃
---------------------------------------------------------------------------------------------------*/














string A, B;
//---------------------------------------------------------------------------------------------------
enum {
    NORMAL,
    QUESTION,
    STAR
};
//---------------------------------------------------------------------------------------------------
vector<pair<int,char>> parse(string s) {
    int n = s.length();
    vector<pair<int,char>> res;
    rep(i, 0, n) {
        if(i + 1 < n and s[i + 1] == '?') {
            res.push_back({QUESTION, s[i]});
            i++;
        } else if(i + 1 < n and s[i + 1] == '*') {
            res.push_back({STAR, s[i]});
            i++;
        } else res.push_back({NORMAL, s[i]});
    }
    return res;
}
//---------------------------------------------------------------------------------------------------
int dp[2010][2010];
void _main() {
    cin >> A >> B;

    auto AA = parse(A);
    auto BB = parse(B);

    int NA = AA.size();
    int NB = BB.size();

    rep(a, 0, NA + 1) rep(b, 0, NB + 1) dp[a][b] = inf;
    dp[0][0] = 0;

    rep(a, 0, NA) rep(b, 0, NB) {
        if (AA[a].first == NORMAL) chmin(dp[a + 1][b], dp[a][b] + 1);
        else chmin(dp[a + 1][b], dp[a][b]); // ?の場合は0コストで消せる

        if (BB[b].first == NORMAL) chmin(dp[a][b + 1], dp[a][b] + 1);
        else chmin(dp[a][b + 1], dp[a][b]); // ?の場合は0コストで消せる

        if(AA[a].first == NORMAL and BB[b].first == NORMAL) {
            chmin(dp[a + 1][b + 1], dp[a][b] + (AA[a].second != BB[b].second));
        }
        if(AA[a].first == NORMAL and BB[b].first == QUESTION) {
            chmin(dp[a + 1][b + 1], dp[a][b] + (AA[a].second != BB[b].second));
        }
        if(AA[a].first == NORMAL and BB[b].first == STAR) {
            chmin(dp[a + 1][b + 1], dp[a][b] + (AA[a].second != BB[b].second));
            chmin(dp[a + 1][b], dp[a][b] + (AA[a].second != BB[b].second)); // *の場合は使っても遷移させないでOK
        }

        if(AA[a].first == QUESTION and BB[b].first == NORMAL) {
            chmin(dp[a + 1][b + 1], dp[a][b] + (AA[a].second != BB[b].second));
        }
        if(AA[a].first == QUESTION and BB[b].first == QUESTION) {
            chmin(dp[a + 1][b + 1], dp[a][b] + (AA[a].second != BB[b].second));
        }
        if(AA[a].first == QUESTION and BB[b].first == STAR) {
            chmin(dp[a + 1][b + 1], dp[a][b] + (AA[a].second != BB[b].second));
            chmin(dp[a + 1][b], dp[a][b] + (AA[a].second != BB[b].second)); // *の場合は使っても遷移させないでOK
        }

        if(AA[a].first == STAR and BB[b].first == NORMAL) {
            chmin(dp[a + 1][b + 1], dp[a][b] + (AA[a].second != BB[b].second));
            chmin(dp[a][b + 1], dp[a][b] + (AA[a].second != BB[b].second));
        }
        if(AA[a].first == STAR and BB[b].first == QUESTION) {
            chmin(dp[a + 1][b + 1], dp[a][b] + (AA[a].second != BB[b].second));
            chmin(dp[a][b + 1], dp[a][b] + (AA[a].second != BB[b].second));
        }
        if(AA[a].first == STAR and BB[b].first == STAR) {
            chmin(dp[a + 1][b + 1], dp[a][b] + (AA[a].second != BB[b].second));
            chmin(dp[a + 1][b], dp[a][b] + (AA[a].second != BB[b].second)); // *の場合は使っても遷移させないでOK
            chmin(dp[a][b + 1], dp[a][b] + (AA[a].second != BB[b].second)); // *の場合は使っても遷移させないでOK
        }
    }

    rep(a, 0, NA) {
        if (AA[a].first == NORMAL) chmin(dp[a + 1][NB], dp[a][NB] + 1);
        else chmin(dp[a + 1][NB], dp[a][NB]);
    }

    rep(b, 0, NB) {
        if (BB[b].first == NORMAL) chmin(dp[NA][b + 1], dp[NA][b] + 1);
        else chmin(dp[NA][b + 1], dp[NA][b]);
    }

    cout << dp[NA][NB] << endl;
}





0