AtCoder Beginner Contest 122 D - We Like AGC 誤答コード

問題と提出コードはこちら。

問題

提出コード

#include <bits/stdc++.h>
using namespace std;
using P = pair<int, int>;
using ll = long long;
#define chmin(i, j) i = min(i, j);
#define chmax(i, j) i = max(i, j);
#define rep(i, n) for(int i=0;i<n;i++)
ll N;
ll MOD = 1000000007;
vector<map<string, ll>> memo;
bool ok(string last4) {
  rep(i, 4) {
    string t = last4;
    if(i >= 1) swap(t[i], t[i-1]);
    auto it = t.find("AGC");
    if(it != string::npos) return false;
  }
  return true;
}

ll dfs(int cur, string last3) {
  if(memo[cur][last3]) return memo[cur][last3];
  if(cur == N) return 1;
  ll ret = 0;
  for(auto& c : "ACGT") {
    if(ok(last3 + c)) {
      ret += dfs(cur+1, last3.substr(1, 2) + c);
      ret %= MOD;
    }
  }
  memo[cur][last3] = ret;
  return ret;
}
int main() {
  cin >> N;
  memo.resize(N+1);
  cout << dfs(0, "TTT") << endl;
}