CafeCoder tea004 ANTimatter

かなり雑ですが、解説動画です。 なおジャッジはしてないので、嘘だったりバグがあったらごめんなさい。 (2020/02/01にジャッジサーバが復活し、ACすることは確認しました)

問題リンク

動画

ANTimatter- easy

ANTimatter- hard

実装例

int main()
{
    ll N;
    string s;
    cin >> N >> s;
    vector<vector<vector<ll>>> dp(N + 1, vector<vector<ll>>(N + 5, vector<ll>(N + 5)));
    dp[0][0][0] = 1;
    for (ll i = 0; i < N; i++) {
        for (ll j = 0; j <= N; j++) {
            for (ll k = 0; k <= N; k++) {
                if (s[i] == '<') {
                    if (k == 0) (dp[i + 1][j + 1][k] += dp[i][j][k]) % MOD;
                    else (dp[i + 1][j][k - 1] += dp[i][j][k]) %= MOD;
                }
                else if (s[i] == '>') {
                    (dp[i + 1][j][k + 1] += dp[i][j][k]) %= MOD;
                }
                else {
                    if (k == 0) (dp[i + 1][j + 1][k] += dp[i][j][k]) % MOD;
                    else (dp[i + 1][j][k - 1] += dp[i][j][k]) %= MOD;
                    (dp[i + 1][j][k + 1] += dp[i][j][k]) %= MOD;
                }
            }
        }
    }
    ll res = 0;
    for (ll i = 0; i <= N; i++) {
        for (ll j = 0; j <= N; j++) {
            res += dp[N][i][j] * (i + j) % MOD;
            res %= MOD;
        }
    }
    cout << res << endl;
    return 0;

}

int main()
{
    ll N;
    string s;
    cin >> N >> s;
    vector<vector<ll>> dp1(N + 1, vector<ll>(N + 5));
    vector<vector<ll>> dp2(N + 1, vector<ll>(N + 5));

    dp1[0][0] = 1;

    for (ll i = 0; i < N; i++) {
        for (ll j = 0; j <= N; j++) {
            if (s[i] == '<') {
                if (j != 0) (dp1[i + 1][j - 1] += dp1[i][j]) %= MOD;
                else (dp1[i + 1][j] += dp1[i][j]) %= MOD;
            }
            else if (s[i] == '>') {
                (dp1[i + 1][j + 1] += dp1[i][j]) %= MOD;
            }
            else {
                if (j != 0) (dp1[i + 1][j - 1] += dp1[i][j]) %= MOD;
                else (dp1[i + 1][j] += dp1[i][j]) %= MOD;
                (dp1[i + 1][j + 1] += dp1[i][j]) %= MOD;
            }
        }
    }

    for (ll i = 0; i < N; i++) {
        for (ll j = 0; j <= N; j++) {

            if (s[i] == '<') {
                if (j == 0) {
                    (dp2[i + 1][j] += dp2[i][j] + dp1[i][j]) %= MOD;
                }
                else {
                    (dp2[i + 1][j - 1] += dp2[i][j]) %= MOD;
                }
            }
            else if (s[i] == '>') {
                (dp2[i + 1][j + 1] += dp2[i][j]) %= MOD;
            }
            else {
                if (j == 0) {
                    (dp2[i + 1][j] += dp2[i][j] + dp1[i][j]) %= MOD;
                }
                else {
                    (dp2[i + 1][j - 1] += dp2[i][j]) %= MOD;
                }
                (dp2[i + 1][j + 1] += dp2[i][j]) %= MOD;
            }
        }
    }


    ll res = 0;

    for (ll i = 0; i <= N; i++) {
        res += (dp2[N][i] + i * dp1[N][i] % MOD) % MOD;
        res %= MOD;
    }
    cout << res << endl;
    return 0;

}