問題一覧 > 通常問題

No.422 String Change (Hard)

レベル : / AI推定難易度 : 1850 / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : (AC するまで非表示) / 解いたユーザー数 34
作問者 : ciel / テスター : uwi
お気に入りにしたユーザー ProblemId : 627 / 自分の提出
問題文最終更新日: 2026-06-28 01:50:46
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 148 (順位表) の他の問題:
Note
This problem is a harder version of No.225 String Change (medium).

Problem Statement

You are given a string \(S\) of length \(n\) and a string \(T\) of length \(m\). Each character of the strings is one of 'A','T','G','C'.
Now, you want to convert \(S\) into \(T\) by successively performing any of the following three types of operations.
(Operations)
[Substitution] Choose one character \(S\)[ i ] from \(S\) and replace it with any character of your choice among 'A','T','G','C'. This costs 5.
[Deletion] Delete any substring from \(S\). The string is allowed to become empty as a result of the deletion. If the number of deleted characters is \(N\), this costs \(9+2*(N-1)\).
[Insertion] Insert a string consisting of 'A','T','G','C' at any position of your choice in \(S\). In particular, characters can also be inserted at the beginning or the end of S. If the number of inserted characters is \(N\), this costs \(9+2*(N-1)\).

Among such sequences of operations, consider one with the minimum total cost. Write a program that outputs that minimum value and the method, expressed as an alignment.
An alignment is the result of applying only insertion and deletion operations to each of the strings;
an insertion is shown as '-' at the insertion position in the string on the $S'$ side, and a deletion is shown as '-' at the deleted position in the string on the $T'$ side.

Input

\(n\) \(m\)
\(S\)
\(T\)

The first line contains the integers \(n\), \(m\), representing the lengths of the strings \(S\), \(T\), separated by a space.
The following second and third lines contain the strings \(S\), \(T\), respectively.

\(1 \leq n, m \leq 1200\)
\(S\), \(T\) are strings consisting of 'A','T','G','C'.

Output

Line 1: the minimum cost
Lines 2 / 3: the alignments $S'$,$T'$, respectively
Print a newline at the end.

There may be multiple alignments that achieve the minimum cost. In that case, you may output any of them.

Sample

Sample 1
Input
20 24
GAGTGGATCTGCGAATCTTG
GAGTTCTGTACTAAGCGCCGTGTC
Output
61
GAGTGGATCTG--CGAATC-----TTG
GAGT---TCTGTACTAAGCGCCGTGTC

Substitutions are denoted by "*", and deletions and insertions by "|".

GAGTGGATCTG--CGAATC-----TTG
GAGT---TCTGTACTAAGCGCCGTGTC

    |||    || *  * |||||* *
    13+    11+5+ 5+17+  5+5
The costs are incurred as shown above, for a total of 61.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。