perogram

D - We Like AGC 〜反省〜

Quiz

https://atcoder.jp/contests/abc122/tasks/abc122_d

Submit (コンテスト後に解説放送を見てからAC)

https://atcoder.jp/contests/abc122/submissions/4704750

解法

解説放送とeditorialで十分なので省略

コンテスト中

DP感
直前の3文字だけを見ればいいので、dp[i][a][b][c]
ここまではできた
[a][b][c]を埋める時に3重ループに縛られすぎたのが敗因
文字のパターンを考えるときに4重ループしてパターンに合わない時に足しこみを除外するのがシンプル
私は下記コードのように、最初はチェックなしに足して、その直後にチェックでNGのものを引いた
- 余事象に似た考えは良さそう
しかし手元のサンプルケースすら通らず

反省・学び

DPで足しこんでから不要なのを引くのは危険かも
a = 0, g = 1, c = 2, t = 3 としたのは、使い所が良ければいいかも
DPで足し込み前にチェックしてcontinueではじくのは良い

なぜか間違っているコード

#include<algorithm>
#include<complex>
#include<ctype.h>
#include<iomanip>
#include<iostream>
#include<fstream>
#include<map>
#include<math.h>
#include<numeric>
#include<queue>
#include<set>
#include<stack>
#include<stdio.h>
#include<string>
#include<string>
#include<vector>

using namespace std;
typedef long long ll;

#define FOR(i,a,b) for(ll i=(a);i<(b);++i)
#define ALL(v) (v).begin(), (v).end()
#define p(s) cout<<(s)<<endl
#define p2(s, t) cout << (s) << " " << (t) << endl
#define br() p("")
#define pn(s) cout << (#s) << " " << (s) << endl
#define p_yes() p("Yes")
#define p_no() p("No")

const ll mod = 1e9 + 7;
const ll inf = 1e18;

template < typename T >
void vprint(T &V){
    for(auto v : V){
        cout << v << " ";
    }
    cout << endl;
}

ll dp[110][4][4][4] = {};

ll to_plus(ll a){
    if(a>=0){
        return a;
    }else{
        ll n = -a / mod;
        n+=5;
        a += n*mod;
        return a;
    }
}

char toc(ll v){
    if(v==0) return 'a';
    if(v==1) return 'g';
    if(v==2) return 'c';
    if(v==3) return 't';
    return '-';
}

ofstream of;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    of.open("log.txt");

    ll a = 0;
    ll g = 1;
    ll c = 2;
    ll t = 3;

    // input
    ll N;
    cin >> N;

    FOR(i, 0, 4){
        FOR(j, 0, 4){
            FOR(k, 0, 4){
                dp[2][i][j][k] = 1;
            }
        }
    }
    // agc
    dp[2][a][g][c] = 0;
    dp[2][a][c][g] = 0;
    dp[2][g][a][c] = 0;

    FOR(i, 3, N){
        FOR(l, 0, 4){
            FOR(m, 0, 4){
                FOR(n, 0, 4){
                    dp[i][l][m][n] += dp[i-1][0][l][m] + dp[i-1][1][l][m] + dp[i-1][2][l][m] + dp[i-1][3][l][m];
                    dp[i][l][m][n] %= mod;
                }
            }
        }

        // A*GC
        // AAGC
        dp[i][a][g][c] -= dp[i-1][a][a][g];
        // AGGC
        dp[i][g][g][c] -= dp[i-1][a][g][g];
        // ACGC
        dp[i][c][g][c] -= dp[i-1][a][c][g];
        // ATGC
        dp[i][t][g][c] -= dp[i-1][a][t][g];

        // AG*C
        // AGAC
        dp[i][g][a][c] -= dp[i-1][a][g][a];
        // AGGC
        dp[i][g][g][c] -= dp[i-1][a][g][g];
        // AGCC
        dp[i][g][c][c] -= dp[i-1][a][g][c];
        // AGTC
        dp[i][g][t][c] -= dp[i-1][a][g][t];

        dp[i][a][g][c] = 0;
        dp[i][a][c][g] = 0;
        dp[i][g][a][c] = 0;

        FOR(l, 0, 4){
            FOR(m, 0, 4){
                FOR(n, 0, 4){
                    dp[i][l][m][n] = to_plus(dp[i][l][m][n]);
                    of << toc(l) << " " << toc(m) << " " << toc(n) << " " << dp[i][l][m][n] << endl; // log
                }
            }
        }

    }

    ll sum = 0;
    FOR(l, 0, 4){
        FOR(m, 0, 4){
            FOR(n, 0, 4){
                sum += dp[N-1][l][m][n];
                sum %= mod;
            }
        }
    }

    p(sum);

    return 0;
}