ABC122 D - We Like AGC

1 min read

前回のコンテスト,ABC122の復習メモを残しておく.

問題

問題文

整数 $N$ が与えられます。次の条件を満たす長さ $N$ の文字列の数を $10^9$ で割った余りを求めてください。

  • A, C, G, T 以外の文字を含まない。
  • AGC を部分文字列として含まない。
  • 隣接する 2 文字の入れ替えを 1 回行うことで上記の条件に違反させることはできない。

制約

  • $3\leq N\leq100$

解法(考え方)

単純な全探索の計算量は $O(4^N)$ .しかし「隣り合う文字列を入れ替えた時に"AGC"を含んではいけない」という制約は,新しくi番目の文字を決定するには直前の3文字のみが関与することがわかる.

ダメなケースというのは例えば

  • 3文字: “AGC”, “GAC”, “ACG”
  • 4文字: “A?GC”, “AG?C”

であるが,コツとして,文字列が制約を守っているかどうかを↑のように自分でパターンを書き出しすのではなく,プログラムしてあげるほうが良いということ(公式の解答でやられている).こういう感じ.

これがまた,Goだと string は要素の入れ替えができなくて辛い感じになるのですが笑(まぁ全角文字が入ったりするとstringの要素はきちんと1文字に対応しないので,できない方が良いとも言える?).

あとはオーバーフローするので余りを取ることを忘れないようにすること.dpテーブルの構築時,最後の和を取る部分の両方で使う.

DPによる解法

解法の方向性がわかったところで,DPで解く方法を考える.この場合,i番目に文字jを採用できる場合の数をテーブルに埋めていく.

制約の全くない単純な数え上げをするケースをまず考えると,遷移式は

$$ dp[i+1][j] = \sum_{k} dp[i][k] $$

のように書くことができ,コードは次のようになる.

この基本形を意識しながら,直前の3文字の状態を保持するためにテーブルを dp[i][j][k][l] のように拡張する.添字はそれぞれ直近3番目(j),直近2番目(k),直近1番目(l)を示す.そうすると遷移式は次のようにかける.

$$ dp[i+1][k][l][m] = \sum_{j,k,l}dp[i][j][k][l] $$

ここで,j k l m の4つの文字を並べたときに,先のokに渡してtrueとなるもののみを遷移可能として足せば良い.dpを使うことで計算量は $O(N)$ になる.for文が多くて結構つらいが完成してみると難しいところは特にない.初期値をどうするかは割と迷った.

メモ化による解法

これは模範解答のpdfと同じなので改めて説明する必要もないけれど,自分で理解する用で書いてみた.メモ化の方が再帰を使うのですっきり書ける.

感想

この手の問題は経験値な気がする.解けるようになるのは楽しいけど,きちんと各解法を理解して,何故これで高速化できるのか,どれくらい高速化されるのかを説明できなければ,実務ではかすりもしない気がする.精進.

comments powered by Disqus

こちらの記事もどうぞ