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

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

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

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

問題へのリンク

問題概要

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

制約

  •  3 \le N \le 100

考えたこと

問題の条件は

  • "AGC"
  • "GAC"
  • "ACG"
  • "AGC" ( は任意)
  • "AGC" ( は任意)

のいずれも含まないことと言い換えられる。こういう禁止文字列系の問題は最悪 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;
}