読者です 読者をやめる 読者になる 読者になる

pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

TopCoder SRM 682 (Div. 2) Medium. TopBiologist

解法

長さ n の文字列の部分文字列は n*(n+1)/2 個しかない。

長さが短い順に A,G,C,T,AA,AG,AC,AT,GA,... という文字列を n*(n+1)/2+1 個列挙すれば、その中には必ず部分文字列ではないものが含まれる。


実際には長さ 12 以下の部分文字列しか考えないので、n*(n+1)/2 個列挙する前に見つかる。

TopCoder SRM 682 (Div. 2) Medium. TopBiologist

部分文字列を全部 set に突っ込んで判定しようと思ったら MLE しました。