こういうの素早く書けるようになるにはどうしたらいいんだろう...

問題概要

'A', 'G', 'C', 'T' のみからなる長さ $N$ の文字列のうち、「どの隣接した 2 文字を swap しても "AGC" を連続部分列として含まないもの」が何通りあるか求めよ。

制約

$3 \le N \le 100$

考えたこと

問題の条件は

"AGC"
"GAC"
"ACG"
"A＊GC" (＊は任意)
"AG＊C" (＊は任意)

のいずれも含まないことと言い換えられる。こういう禁止文字列系の問題は最悪 trie 木で直近文字列の遷移状態を管理するような DP でできる (蟻本に載ってる) が、ここでは

「直近 3 文字がわかっていれば、それより前の文字列の情報は要らない」

ということによって、簡単な DP でできる。

dp[ n ][最後の前の前の文字][最後の前の文字][最後の文字] := 長さ n の文字列が何通り作れるか

とした。文字として

0: dammy (DP を初期化するのにこれがあると便利)
1: A
2: G
3: C
4 : T

の 5 種類を割り当てた。dammy を用意すれば初期条件を

dp[0][0][0][0] = 1

と表せる。遷移は

    for (int n = 0; n < N; ++n) {
        for (int i = 0; i < 5; ++i) {
            for (int j = 0; j < 5; ++j) {
                 for (int k = 0; k < 5; ++k) {
                     for (int l = 1; l < 5; ++l) {
                         if (i == 1 && j == 2 && l == 3) continue;
                         if (i == 1 && k == 2 && l == 3) continue;
                         if (j == 1 && k == 2 && l == 3) continue;
                         if (j == 2 && k == 1 && l == 3) continue;
                         if (j == 1 && k == 3 && l == 2) continue;
                         add(dp[n+1][j][k][l], dp[n][i][j][k]);
                     }
                }
            }
        }
    }

という感じに書いた。最後に多次元 DP を多次元 vector de 宣言する便利な方法がこの記事にあるので参考にした。

#include <iostream>
#include <vector>
using namespace std;

// 多次元 vector 生成
template<class T>
vector<T> make_vec(size_t a){
    return vector<T>(a);
}
template<class T, class... Ts>
auto make_vec(size_t a, Ts... ts){
  return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}

// mod add
const int MOD = 1000000007;
void add(long long &a, long long b) {
    a += b;
    if (a >= MOD) a -= MOD;
}

// 0: dammy, 1: 'A', 2: 'G', 3: 'C', 4: 'T'
// "AGC, GAC, ACG", "A*GC", "AG*C" を含まない (012, 102, 021 を禁止)
long long solve(int N) {
    auto dp = make_vec<long long>(N+1, 5, 5, 5); // dp[i文字][3文字前][2文字前][1文字前]
    dp[0][0][0][0] = 1;
    for (int n = 0; n < N; ++n) {
        for (int i = 0; i < 5; ++i) {
            for (int j = 0; j < 5; ++j) {
                 for (int k = 0; k < 5; ++k) {
                     for (int l = 1; l < 5; ++l) {
                         if (i == 1 && j == 2 && l == 3) continue;
                         if (i == 1 && k == 2 && l == 3) continue;
                         if (j == 1 && k == 2 && l == 3) continue;
                         if (j == 2 && k == 1 && l == 3) continue;
                         if (j == 1 && k == 3 && l == 2) continue;
                         add(dp[n+1][j][k][l], dp[n][i][j][k]);
                     }
                }
            }
        }
    }
    long long res = 0;
    for (int i = 1; i < 5; ++i)
        for (int j = 1; j < 5; ++j)
            for (int k = 1; k < 5; ++k)
                add(res, dp[N][i][j][k]);
    return res;
}

int main() {
    int N;
    while (cin >> N) cout << solve(N) << endl;
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 122 D - We Like AGC (水色, 400 点)

問題概要

制約

考えたこと