かなり苦戦。 解法 自明な DP は次のようなもの。 dp[ i 番目まで見た ][ 現在の x 座標 ][ 現在の y 座標 ][ 変更した回数 ] := 原点を通った回数の最大値 しかし O(n4) なので間に合わない。 少し考えると現在の x 座標と y 座標はなくても更新できること…

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