Ex - TGC Triplets

概要

この問題特有の規則性に気付けるかがポイントです．
丁寧に実験をしたり考察をすることで正解できます．

問題原案：uni_kakurenbo

略解

長さを最小にするには，$6$ つめの操作をできるだけ行う必要があります．

A, T, U は，適切に U を経由することでどの文字にも置換が可能です． C, G は互いの文字にしかなることができません．

$6$ つめの操作の対象となる，連続した $3$ 文字は，A, T, U で始まっていなければなりません．
逆に，後ろの $2$ 文字は何であっても問題ないことが分かります．

操作後の文字は AC であり，これは頭文字を T に置換できます．
よって，最初に出現する A, T, U のいずれかで始まる，長さが $3$ 以上の連続部分文字列はすべて操作を行う対象になります．

$P \coloneqq \{$C$,\,$G$\}, Q \coloneqq \{$A$,\,$T$,\,$U$\}$ とします．

操作後の文字列を作り(末尾を AC で置き換えて)，$P$ に属するなら $2$ をかけて，$Q$ に属するなら $5$ を掛ければコーナーケースにも対応できます．

一度も操作ができない場合に注意してください．

解説

$Ⅰ.$ 概略

文字列の長さが減少する操作は $6$ つ目のもの(TGC → AC)のみです．

また，文字 U は任意の文字へ変換でき，A, T についても U を経由することで任意の文字に変換できます．G は C へ変換できます．
ゆえに，長さが $n$ の任意な文字列から，CCC..CC といったように C が $n$ 個連なった文字列を作ることができます．

さらに，文字列 CCC..CC の先頭へ T を追加した文字列 TCCC..CC は，TGCC..C と変換でき，TGC の部分は AC を経由して TG に変換できるため，結果的に TGCC..CC から TGCC..C (C が一つ少ない文字列) を作ることができます．

したがって，再帰的に考えると，X を任意の文字として，適当な長さの文字列 TXXXXX..X から，長さ $2$ の文字列 AC を作ることができます．

以上のことと，A, U を T へ変換できることを踏まえると，文字列 $S$ において最初に現れる G, C 以外の文字の位置を $k$ とするとき，
$S$ のうちで $k$ 以降の文字列は AC へと変換でき，残った長さ $k + 1$ の文字列が最小になるということが示せます．
(C, Gのみからなる文字列に操作を行って T を含むようにすることはできない．)

残った文字列の形は，P を C, G のいずれかとして，PP..PPAC となります．

P に当てはまるものの選び方は，$2^{k-1}$ 通り，
A は任意の文字へ変換できるため，$5$ 通り，
末尾の C は G に変換できるため $2$ 通り
となります．

以上より，答えは $2^{k-1} \times 5\ \times 2 = 5 \times 2^k$ 通り $(\bmod\;{998244353})$ です．

P を C, G のいずれか，Q を A, T, U のいずれかとして，$S$ が PP...PP のときと PP..PPQQ のときがコーナーケースとなります．
(前者は $2^{|S|}$，後者は $25 \times 2^{k-1}$)

実装時には，操作後の文字列を実際に生成することで，これらのコーナーケースにも対応可能です．

$Ⅱ.$ 発展

$1)$ 類題

• ARC 140 $\hspace{0.15em}$ B - Shorten ARC

実装例

$\\$

余談

トリを飾る問題ですから，TGC を題材にしたいという思いで作問しました．
TGC, よくよく見てみるとすべて有名な塩基の略称として存在するんですよね．

これは使うしかないと思いました()

ARC-A のような問題も作ってみたいという思いがあったため，最終的にこのような形となりました．
実装量は極力少なくしたつもりです．

楽しんでいただけたでしょうか？