結果

問題 No.225 文字列変更(medium)
コンテスト
ユーザー syaro
提出日時 2018-01-10 20:52:13
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 11 ms / 5,000 ms
コード長 3,343 bytes
コンパイル時間 1,968 ms
コンパイル使用メモリ 175,336 KB
実行使用メモリ 10,752 KB
最終ジャッジ日時 2024-12-23 17:05:13
合計ジャッジ時間 2,761 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

// https://yukicoder.me/problems/610
#include <bits/stdc++.h>
using namespace std;

#define times(n, i)      uptil(0, n, i)
#define rtimes(n, i)     downto((n) - 1, 0, i)
#define upto(f, t, i)    for(decltype(t) i##0_to = (t), i = (f); i <= i##0_to; i++)
#define uptil(f, t, i)   for(decltype(t) i##0_to = (t), i = (f); i <  i##0_to; i++)
#define downto(f, t, i)  for(decltype(f) i##0_to = (t), i = (f); i >= i##0_to; i--)
#define downtil(f, t, i) for(decltype(f) i##0_to = (t), i = (f); i >  i##0_to; i--)
// types
    typedef long double LD;
    #define long long long
    #define int long
    using VI = vector<int>;
    using WI = vector<VI>;
    using PI = pair<int, int>;
    using VPI = vector<PI>;
    using WPI = vector<VPI>;

bool debug;
#define _GLIBCXX_DEBUG
#define _LIBCPP_DEBUG 2
#define _LIBCPP_DEBUG2 2
#define ln << '\n'
#define tb << '\t'
#define sp << ' '
#define db(x) if(debug) cerr << #x << " = " << (x) << ", "
#define dbg(x) if(debug) cerr << #x << " = " << (x) ln

constexpr long INF = 1LL << 60;

void solve();

signed main(signed argc, char *argv[]) {
    #ifdef EBUG
        debug = true;
    #elif defined(ONLINE_JUDGE)
        debug = false;
    #else
        debug = argc >= 2;
    #endif
    if(!debug) {
        cin.tie(0);
        ios::sync_with_stdio(0);
    }
    cout << fixed << setprecision(20);
    cerr << fixed << setprecision(20);

    solve();

    return 0;
}

/******************************* basic library ********************************/
// IO
    template<class T>
    istream& operator>>(istream& s, vector<T>& v) {
        for(auto&& p : v) s >> p; return s;
    }
    template<class T>
    ostream& operator<<(ostream& s, vector<T> v) {
        int i = 0;
        for(const auto& p : v) s << (i++?" ":"") << p;
        return s;
    }
    template<class T>
    ostream& operator<<(ostream& s, vector<vector<T>> w) {
        for(const auto& v : w) {
            int i = 0;
            for(const auto& p : v) s << (i++?" ":"") << p;
            s ln;
        }
        return s;
    }
    template<class T, class... A>
    T RD(A... a) { T t(a...); cin >> t; return t; }
// other
#define all(x) (x).begin(), (x).end()
#define b_max(x, y) x = max(x, y)
#define b_min(x, y) x = min(x, y)
inline LD AC(LD d) { return d ? d : 0; }

/****************************** optional library ******************************/
//-mod constexpr long MOD = 1000000009; // 1000000007; // 998244353;
//-math
//-rmq
//-dfs
//-sparse_table(fn,nil=min,INF)

//+string/edit_distance
	template<class T> int edit_distance(
		vector<T> a, vector<T> b,
		int ins = 1, int sub = 1, int pass = 0
	) {
		if(ins < 0) { db(ins); dbg(ins >= 0); }
		if(sub < 0) { db(sub); dbg(sub >= 0); }
		if(pass > 0) { db(pass); dbg(sub <= 0); }
		int x = a.size(), y = b.size();
		WI dp(x + 1, VI(y + 1));
		upto(1, x, i) dp[i][0] = dp[i-1][0] + ins;
		upto(1, y, j) dp[0][j] = dp[0][j-1] + ins;
		upto(1, x, i) upto(1, y, j) {
			dp[i][j] = min({
				dp[i-1][j] + ins,
				dp[i][j-1] + ins,
				dp[i-1][j-1] + (a[i-1] == b[j-1] ? pass : sub),
			});
		}

		return dp[x][y];
	}


/************************************ main ************************************/


void solve() {
    auto N = RD<int>(), M = RD<int>();
    auto S = RD<string>(), T = RD<string>();
    vector<char> s(all(S)), t(all(T));
    cout << edit_distance(s, t) ln;
}
0