raahii.meのブログのロゴ画像

ウェブログ

ABC122 D - We Like AGC

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

問題

問題文

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

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

制約

  • 3N1003\leq N\leq100

解法(考え方)

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

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

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

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

{{< gist raahii 1f5d88bda3ec4b09e26aeb55b48f3ca8 >}}

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

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

DPによる解法

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

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

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

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

{{< gist raahii 3a69a715536f5e451e9bc3c491632590 >}}

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

dp[i+1][k][l][m]=j,k,ldp[i][j][k][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)O(N) になる.for文が多くて結構つらいが完成してみると難しいところは特にない.初期値をどうするかは割と迷った.

{{< gist raahii 019732bf3d8bccd5a0a8f2764a5d4169 >}}

メモ化による解法

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

{{< gist raahii ea62641e1f2ba6d9cbfa6aac777914e8 >}}

感想

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