#1168812 (C++23) No.422 文字列変更 (Hard)

• 問題: No.422 文字列変更 (Hard)
• ユーザー: kwm_t
• 提出日時: 2026-06-10 19:51:00
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 79 ms / 3,000 ms
• コード長: 3,322 bytes
• コンパイル時間: 3,337 ms
• コンパイル使用メモリ: 346,828 KB
• 実行使用メモリ: 104,960 KB
• 最終ジャッジ日時: 2026-06-10 19:51:06
• 合計ジャッジ時間: 5,308 ms
• ジャッジサーバーID （参考情報）: judge2_1 / judge1_0

ファイルパターン	結果
sample	AC * 1
other	AC * 16

ソースコード

#include <bits/stdc++.h>
//#include <atcoder/all>
using namespace std;
// using namespace atcoder;
// using mint = modint1000000007;
// const int mod = 1000000007;
// using mint = modint998244353;
// const int mod = 998244353;
// const int INF = 1e9;
// const long long LINF = 1e18;
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep2(i, l, r) for (int i = (l); i < (r); ++i)
#define rrep(i, n) for (int i = (n)-1; i >= 0; --i)
#define rrep2(i, l, r) for (int i = (r)-1; i >= (l); --i)
#define all(x) (x).begin(), (x).end()
#define allR(x) (x).rbegin(), (x).rend()
#define P pair<int, int>
template<typename A, typename B> inline bool chmax(A &a, const B &b) { if (a < b) { a = b; return true; } return false; }
template<typename A, typename B> inline bool chmin(A &a, const B &b) { if (a > b) { a = b; return true; } return false; }

struct Prev {
	int pi, pj, ps;
	char op; // M:match/replace, D:delete, I:insert
};

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	// 実装はAIに投げました
	int n, m;
	string S, T;
	cin >> n >> m;
	cin >> S;
	cin >> T;

	const long long INF = (long long)4e18;

	vector dp(n + 1, vector<array<long long, 3>>(m + 1));
	vector pre(n + 1, vector<array<Prev, 3>>(m + 1));

	for (int i = 0; i <= n; i++) {
		for (int j = 0; j <= m; j++) {
			for (int s = 0; s < 3; s++) {
				dp[i][j][s] = INF;
			}
		}
	}

	dp[0][0][0] = 0;

	auto relax = [&](int ni, int nj, int ns,
		long long nd,
		int pi, int pj, int ps,
		char op) {
			if (nd < dp[ni][nj][ns]) {
				dp[ni][nj][ns] = nd;
				pre[ni][nj][ns] = { pi, pj, ps, op };
			}
	};

	for (int i = 0; i <= n; i++) {
		for (int j = 0; j <= m; j++) {

			// match / replace
			if (i < n && j < m) {
				long long cost = (S[i] == T[j] ? 0 : 5);

				for (int st = 0; st < 3; st++) {
					if (dp[i][j][st] == INF) continue;
					relax(
						i + 1, j + 1, 0,
						dp[i][j][st] + cost,
						i, j, st,
						'M'
					);
				}
			}

			// delete one more character from S
			if (i < n) {
				for (int st = 0; st < 3; st++) {
					if (dp[i][j][st] == INF) continue;

					long long add;
					if (st == 1) add = 2;     // extend deletion gap
					else add = 9;           // open deletion gap

					relax(
						i + 1, j, 1,
						dp[i][j][st] + add,
						i, j, st,
						'D'
					);
				}
			}

			// insert one more character from T
			if (j < m) {
				for (int st = 0; st < 3; st++) {
					if (dp[i][j][st] == INF) continue;

					long long add;
					if (st == 2) add = 2;     // extend insertion gap
					else add = 9;           // open insertion gap

					relax(
						i, j + 1, 2,
						dp[i][j][st] + add,
						i, j, st,
						'I'
					);
				}
			}
		}
	}

	long long ans = INF;
	int state = -1;

	for (int s = 0; s < 3; s++) {
		if (dp[n][m][s] < ans) {
			ans = dp[n][m][s];
			state = s;
		}
	}

	string SA, TA;

	int i = n, j = m, s = state;

	while (!(i == 0 && j == 0)) {
		Prev p = pre[i][j][s];

		if (p.op == 'M') {
			SA.push_back(S[p.pi]);
			TA.push_back(T[p.pj]);
		}
		else if (p.op == 'D') {
			SA.push_back(S[p.pi]);
			TA.push_back('-');
		}
		else { // 'I'
			SA.push_back('-');
			TA.push_back(T[p.pj]);
		}

		i = p.pi;
		j = p.pj;
		s = p.ps;
	}

	reverse(SA.begin(), SA.end());
	reverse(TA.begin(), TA.end());

	cout << ans << '\n';
	cout << SA << '\n';
	cout << TA << '\n';

	return 0;
}