これはなに？
注意
テストケース
B 問題との違い
large で正の点を取る解法
改善のヒント
おまけ1 - 無限に文字列長くできそうにみえるけど、ジャッジは大丈夫なの？
おまけ2 - リポジトリ
おまけ3 - マラソンの基本？である複数のテストケースで確かめる。
おまけ4 - 質問

これはなに？

ゲノコン2021 ー DNA配列解析チャレンジが AtCoder 上で行われています。

参加者は 500 人を超えるという素晴らしい事実に対して、練習問題である C 問題で large で正の点数を獲得している人は 2 割も現時点ではいません。

そこで、この記事では、まず large で正の点をとり、 3000 を超えるための足掛かりとなるような入門記事を目指します。

注意

B 問題が AC できていることを前提にしています。B 問題が解けていない人は解説記事を読んでみてください。
いろいろ既存手法が存在するらしいですが、私は一切知りません。しかし、B 問題さえ AC できているなら 3000 点を超える足がかりとなる記事を目指しています。実際、私はここで述べた手法の改善で 3319 を達成しています ( 記事執筆時 13 位相当 )

テストケース

テストケースの生成手法に注目してみましょう。

参照ゲノム配列の一部（ヒトの 22 番染色体）から部分文字列 s を切り出す．ただし，A, T, G, C 以外の文字が含まれている領域は切り出しの対象としない．切り出した部分文字列に対して，シークエンサーの読み取りを模したエラー（挿入，欠損，置換）を発生させた文字列 s を生成する．これを複数回繰り返して，一つのテストケースとする．なお，テストケースにはsは含まれない．どのようにしてシークエンサーの読み取りエラーを模したかは非公開とするが，サンプルデータセットは以下よりダウンロードできる．

つまり、一つの文字列を改変した文字列が $m$ 個存在し、それらの列ベクトルをできるだけ揃えたいという問題になることが理解できます。

B 問題との違い

実際に入力としては与えられませんが、 $m = 2$ の場合を考えてみましょう。 B 問題と決定的に違う点が 1 つあります。 C 問題では、('-', '-') のペアが損にはなりません。

つまり、文字列を長くしても損ではなく、列ベクトルの中で、異なる文字を減らすことが大切だということがわかります。B 問題の sim 関数を以下のように置き換えて問題を解くのが C 問題では最善となります。

x/y	A	C	G	T	-
A	0	-1	-1	-1	-1
C	-1	0	-1	-1	-1
G	-1	-1	0	-1	-1
T	-1	-1	-1	0	-1
-	-1	-1	-1	-1	0

large で正の点を取る解法

$m = 2$ の場合で解くことができたので、あとはこれの延長です。

1 つの文字列に着目します。ここでは、 $s _ {1}$ に着目することにします。
$i = 2, 3, ..., m$ の順に、上の sim 関数で $s = s _ {1}$ , $t = s _ {i}$ とした時の B 問題を解いていき、 $s _ {1}$ と $s _ {i}$ を更新していきます。
$s _ {i}$ の文字列長が一致していません。このとき、必ず $s _ {1}$ が最長の文字列になっています ( 理由がわからない人は考えてみましょう ) 。最後に $i = 2, 3, ..., m$ の順に、上の sim 関数で $s = s _ {1}$ , $t = s _ {i}$ かつ文字列 $s$ には - が追加できない時の B 問題を解きます。これで文字列長が一致します。