結果

問題 No.422 文字列変更 (Hard)
コンテスト
ユーザー lam6er
提出日時 2025-04-09 21:04:54
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,019 bytes
コンパイル時間 196 ms
コンパイル使用メモリ 82,416 KB
実行使用メモリ 145,756 KB
最終ジャッジ日時 2025-04-09 21:06:36
合計ジャッジ時間 7,248 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 15 WA * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

n, m = map(int, input().split())
s = input().strip()
t = input().strip()

INF = float('inf')

# Initialize DP tables
M = [[INF] * (m + 1) for _ in range(n + 1)]
D = [[INF] * (m + 1) for _ in range(n + 1)]
I = [[INF] * (m + 1) for _ in range(n + 1)]

M[0][0] = 0  # Base case

for i in range(n + 1):
    for j in range(m + 1):
        # Compute M[i][j]
        if i > 0 and j > 0:
            replace_cost = 0 if s[i-1] == t[j-1] else 5
            min_prev = min(M[i-1][j-1], D[i-1][j-1], I[i-1][j-1])
            M[i][j] = min_prev + replace_cost
        # Compute D[i][j] (deletions)
        if i > 0:
            candidates = []
            if M[i-1][j] != INF:
                candidates.append(M[i-1][j] + 9)
            if D[i-1][j] != INF:
                candidates.append(D[i-1][j] + 2)
            if candidates:
                D[i][j] = min(candidates)
        # Compute I[i][j] (insertions)
        if j > 0:
            candidates = []
            if M[i][j-1] != INF:
                candidates.append(M[i][j-1] + 9)
            if I[i][j-1] != INF:
                candidates.append(I[i][j-1] + 2)
            if candidates:
                I[i][j] = min(candidates)

# Determine the minimal cost
min_cost = min(M[n][m], D[n][m], I[n][m])

# Backtrack to find the alignment
s1 = []
s2 = []
i, j = n, m

current = None
if min_cost == M[n][m]:
    current = 'M'
elif min_cost == D[n][m]:
    current = 'D'
else:
    current = 'I'

while i > 0 or j > 0:
    if current == 'M':
        s1.append(s[i-1])
        s2.append(t[j-1])
        replace_cost = 0 if s[i-1] == t[j-1] else 5
        prev_val = M[i][j] - replace_cost
        i -= 1
        j -= 1
        # Find previous state
        if i >= 0 and j >= 0:
            if M[i][j] == prev_val:
                current = 'M'
            elif D[i][j] == prev_val:
                current = 'D'
            else:
                current = 'I'
    elif current == 'D':
        s1.append(s[i-1])
        s2.append('-')
        current_val = D[i][j]
        i -= 1
        # Determine previous state
        if i >= 0:
            candidate1 = M[i][j] + 9
            candidate2 = D[i][j] + 2
            if current_val == candidate1:
                current = 'M'
            elif current_val == candidate2:
                current = 'D'
            else:
                current = None  # Error case, should not happen
    elif current == 'I':
        s1.append('-')
        s2.append(t[j-1])
        current_val = I[i][j]
        j -= 1
        # Determine previous state
        if j >= 0:
            candidate1 = M[i][j] + 9
            candidate2 = I[i][j] + 2
            if current_val == candidate1:
                current = 'M'
            elif current_val == candidate2:
                current = 'I'
            else:
                current = None  # Error case, should not happen

# Reverse to get the correct order
s1.reverse()
s2.reverse()

aligned_s = ''.join(s1)
aligned_t = ''.join(s2)

print(min_cost)
print(aligned_s)
print(aligned_t)
0