D - We Like AGC
はじめに
競技プログラミング、AtCoder Beginner Contest 122
D - We Like AGC
言語はC#
何かあればTwitter→@pirorirori_n712まで
問題
問題文
整数 N が与えられます。 次の条件を満たす長さ N の文字列の数を 10~9+7 で割った余りを求めてください。 ・A, C, G, T 以外の文字を含まない。 ・AGC を部分文字列として含まない。 ・隣接する 2 文字の入れ替えを 1 回行うことで上記の条件に違反させることはできない。
注記
文字列 T の部分文字列とは、T の先頭と末尾から 0 文字以上を取り去って得られる文字列です。 例えば、ATCODER の部分文字列には TCO, AT, CODER, ATCODER, (空文字列) が含まれ、AC は含まれません。
制約
・3≤N≤100
入力
入力は以下の形式で標準入力から与えられる。 N
出力
条件を満たす文字列の数を 10^9+7 で割った余りを出力せよ
解き方
以下を参考にしています。
ABC122 D - We Like AGC - ARMERIA
AtCoder ABC 122 D - We Like AGC (400 点) - けんちょんの競プロ精進記録
提出 #4704271 - AtCoder Beginner Contest 122
解き方の流れ
問題文に書かれている条件のうち
以下の2つ目と3つ目
・AGC を部分文字列として含まない。 ・隣接する 2 文字の入れ替えを 1 回行うことで上記の条件に違反させることはできない。
がなければ問題がシンプルになるので
どのような場合に
この条件に引っかかるのかを考えます。
すると以下の文字の並びのとき、
条件にかかることが分かります。
AGC GAC ACG A?GC AG?C
「？」は「何でもいいので何か一文字」を指しています。
上の条件にかかってしまう部分文字列から、
3文字前、2文字前、1文字前、現在の文字を調べ
上の部分文字列と同じになっていたら
そのパターンは数としてカウントしないという方法がとれそうです。
文字列のパターンをカウントしていくには
DPを使用します。
構成要素は以下のようにします。
dp[文字の数][現在の文字から2つ前の文字][現在の文字から1つ前の文字][現在の文字]=「文字の数」でできるパターンの数
そして、
以下のようにループを回しながら
作ることのできる文字列をカウントしていきます。
問題文から文字列を構成するのは
A,G,C,Tの4文字ですが
数字に置き換えるとループの数をそのまま使えるので
A=1,G=2,C=3,T=4と各文字を数字に置き換えています。
また、DPの始点としての文字列が一つ欲しいので
ダミーの文字を一つ追加し、
数字を0と置きました。
始点を全てdummy文字にしています。
（dp[0, 0, 0, 0] = 1;）
参考：AtCoder ABC 122 D - We Like AGC (400 点) - けんちょんの競プロ精進記録
//dummy=0,A=1,G=2,C=3,T=4
var dp = new long[N + 1, 5, 5, 5];
dp[0, 0, 0, 0] = 1;
//文字数
for (int n = 0; n < N; ++n)
{
//3文字前の文字
for (int i = 0; i < 5; ++i)
{
//2文字前の文字
for (int j = 0; j < 5; ++j)
{
//1文字前の文字
for (int k = 0; k < 5; ++k)
{
//現在の文字
for (int l = 1; l < 5; ++l)
{
//AGC GAC ACG A?GC AG?C (i,j,k,l)のパターンをはじく
if (j == 1 && k == 2 && l == 3//AGC
|| j == 2 && k == 1 && l == 3//GAC
|| j == 1 && k == 3 && l == 2//ACG
|| i == 1 && k == 2 && l == 3//A?GC
|| i == 1 && j == 2 && l == 3)//AG?C
{
continue;
}
dp[n + 1, j, k, l] = (dp[n + 1, j, k, l] + dp[n, i, j, k]) % 1000000007;
}
}
}
}
}
現在の文字の「l」だけ範囲が
0～5ではなく1～5になっていますが
これは、
実際に数える際には「dummy」の数字は必要ないから
だと思います。
あと、
これはなぜか分からなかったのですが
「l」の範囲を0～5にすると
値がずれます。
dp[0, 0, 0, 0] = 1 は
1のままで変わらないで欲しいのに
i=0,j=0,k=0,l=0のとき
dp[0, 0, 0, 0] =dp[0, 0, 0, 0] +dp[0, 0, 0, 0] で
dp[0, 0, 0, 0] が2になってしまうからかもしれないです。
あとは、
dummyの0を除いた
1～4でループを回し
DPの中に保存されている
N文字のときのパターンを
足せば答えが出ます。
//パターンの個数を出す
var ans = 0L;
//dummyの0を除いた1～4でループ
for (int i = 1; i < 5; ++i)
{
for (int j = 1; j < 5; ++j)
{
for (int k = 1; k < 5; ++k)
{
//N文字のときのパターンの数が知りたいので文字数はN固定
ans = (ans + dp[N, i, j, k]) % 1000000007;
}
}
}
全体のコード
using System;
using System.Linq;
using System.Collections.Generic;
class Program
{
static void Main()
{
var N = Int32.Parse(Console.ReadLine());
//dummy=0,A=1,G=2,C=3,T=4
var dp = new long[N + 1, 5, 5, 5];
dp[0, 0, 0, 0] = 1;
//文字数
for (int n = 0; n < N; ++n)
{
//3文字前の文字
for (int i = 0; i < 5; ++i)
{
//2文字前の文字
for (int j = 0; j < 5; ++j)
{
//1文字前の文字
for (int k = 0; k < 5; ++k)
{
//現在の文字
for (int l = 1; l < 5; ++l)
{
//AGC GAC ACG A?GC AG?C (i,j,k,l)のパターンをはじく
if (j == 1 && k == 2 && l == 3//AGC
|| j == 2 && k == 1 && l == 3//GAC
|| j == 1 && k == 3 && l == 2//ACG
|| i == 1 && k == 2 && l == 3//A?GC
|| i == 1 && j == 2 && l == 3)//AG?C
{
continue;
}
dp[n + 1, j, k, l] = (dp[n + 1, j, k, l] + dp[n, i, j, k]) % 1000000007;
}
}
}
}
}
//パターンの個数を出す
var ans = 0L;
//dummyの0を除いた1～4でループ
for (int i = 1; i < 5; ++i)
{
for (int j = 1; j < 5; ++j)
{
for (int k = 1; k < 5; ++k)
{
//N文字のときのパターンの数が知りたいので文字数はN固定
ans = (ans + dp[N, i, j, k]) % 1000000007;
}
}
}
Console.WriteLine(ans);
}
}
