ABC122 D - We Like AGC

考えたこと：

1)メモ化再帰

2)包除原理で解く。

-> 2は厳しそう。

-> 重複が滅茶苦茶になりそう。

メモ化再帰で実装する。

どうやって？

dp[i][a][b]：＝i番目まで見ていて、i-2番目はa,i-1番目はbの時の数列の個数。

(ここで、A=0,B=1,C=2,T=3と対応させる。)

これを再帰関数rec(i,a,b)で解く。

ＮＧパターンは

ＡＧＣ、ＡＣＧ、ＧＡＣの３つなので

a=0,b=2のときはi番目はC=2以外の３パターン

(a=0,b=1),(a=2,b=0)のときも同様にする。

しかし・・・

サンプル２が合わない！！

２３３になる！

ここで1時間以上迷走をする・・・

なぜ？

サンプル１で合い、サンプル２で合わない理由。

４文字以上の文字列にのみ存在するＮＧパターンが存在するのでは？

ということに気付く。

上記３つのほかに、AXGC,AGXC　（Ｘ＝A,G,C,T)　の場合にもＮＧとなる。

なので、引数は４つ必要でrec(i,a,b,c)を解くことになる。

実装：

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;

int N;
int dp[110][5][5][5];

int rec(int n, int a, int b, int c) {
  if (n == N) return 1;
  if (dp[n][a][b][c] > 0) return dp[n][a][b][c];

  int res = 0;
  if (a == 0 && b == 2) {
    for (int i = 0; i < 4; i++) {
      if (i != 1) {
        res += rec(n + 1, b, c, i);
        res %= MOD;
      }
    }
  } else if (b == 2 && c == 0) {
    for (int i = 0; i < 4; i++) {
      if (i != 1) {
        res += rec(n + 1, b, c, i);
        res %= MOD;
      }
    }
  } else if (b == 0 && c == 2) {
    for (int i = 0; i < 4; i++) {
      if (i != 1) {
        res += rec(n + 1, b, c, i);
        res %= MOD;
      }
    }
  } else if (b == 0 && c == 1) {
    for (int i = 0; i < 4; i++) {
      if (i != 2) {
        res += rec(n + 1, b, c, i);
        res %= MOD;
      }
    }
  } else if (a == 0 && c == 2) {
    for (int i = 0; i < 4; i++) {
      if (i != 1) {
        res += rec(n + 1, b, c, i);
        res %= MOD;
      }
    }
  } else {
    for (int i = 0; i < 4; i++) {
      res += rec(n + 1, b, c, i);
      res %= MOD;
    }
  }

  return dp[n][a][b][c] = res;
}

signed main() {
  cin >> N;
  cout << rec(0, 3, 3 ,3) << endl;
  return 0;
}

答えは、NGに関係ない３文字の後ろにＮ文字を付けたとき、条件を満たす文字列は何個か？と考えてrec(0,3,3,3)などと答える。

これは　　ＴＴＴ（条件を満たすＮ文字の文字列）　の個数に等しい。

感想：

悔しいです。

全完したかった。

でもレートが上がったので良しとします。