問題一覧 > 通常問題

No.422 文字列変更 (Hard)

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : / 解いたユーザー数 25
作問者 : cielciel / テスター : uwiuwi
0 ProblemId : 627 / 出題時の順位表
問題文最終更新日: 2017-06-25 16:08:14
Note
この問題はNo.225 文字列変更(medium)の強化版です。

問題文

長さ\(n\)の文字列\(S\)と長さ\(m\)の文字列\(T\)が与えられます。文字列を構成する各文字は、'A','T','G','C'のいずれかです。
今、\(S\)に以下の3種類の操作のいずれかを順次実施して\(T\)に変換したいです。
(操作)
【置換】 \(S\)の中から文字\(S\)[ i ]を1個選んで、その文字を'A','T','G','C'のいずれかの好きな文字に置換します。コストが5掛かります。
【削除】 \(S\)から任意の部分文字列を削除します。削除によって空文字列になることも許容します。削除した文字数を\(N\)とすると、\(9+2*(N-1)\)のコストが掛かります。
【挿入】 \(S\)の好きな箇所に、'A','T','G','C'からなる文字列を挿入します。特に、Sの先頭や最後尾に文字を挿入することもできます。挿入した文字数を\(N\)とすると、\(9+2*(N-1)\)のコストが掛かります。

このような一連の操作のうち、合計コストの最小となるものについて、その最小値、およびその方法をアラインメントとして出力するプログラムを書いて下さい。
アラインメントとは、それぞれの文字列に対して挿入・削除操作だけを適用したものとし、
挿入の場合は$S'$側の文字列にその挿入箇所を'-'として表示するものとし、削除の場合は$T'$側の文字列に削除箇所を'-'として表示するものとする。

入力

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

一行目に文字列\(S\), \(T\)の長さを表す整数\(n\), \(m\)で空白区切りで与えられます。
続く二行目、三行目には、文字列\(S\), \(T\)がそれぞれ与えられます。

\(1 \leq n, m \leq 1200\)
\(S\), \(T\)は、'A','T','G','C'から構成される文字列です。

出力

1行目:コストの最小値
2行目/3行目:それぞれ$S'$,$T'$のアラインメント
最後に改行して下さい。

もしかしたら最小コストを満たすアラインメントは複数存在するかもしれません。その場合、どれを出力してもかまいません。

サンプル

サンプル1
入力
20 24
GAGTGGATCTGCGAATCTTG
GAGTTCTGTACTAAGCGCCGTGTC
出力
61
GAGTGGATCTG--CGAATC-----TTG
GAGT---TCTGTACTAAGCGCCGTGTC

置換を「*」、削除・挿入を「|」とします。

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

    |||    || *  * |||||* *
    13+    11+5+ 5+17+  5+5
以上のようにコストが掛かり、合計61です。

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