NDPCやった1

NDPCをやったのでやったところだけ解説書きます
しゃべりながら書きます

A ポリオミノ

A~Cはなぜか電車内だった
まあそこそこ簡単だった
$dp[i]$は横幅iだった時の通り数
計算量は$O(N^2)$

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main(){
    int N;
    cin >> N;
    vector<ll> dp(N+1);

    for (int i = 0; i <= N; i++){
        if (i == 0) dp[i] = 1;
        else if (i == 1) dp[i] = 1;
        else if (i == 2) dp[i] = 2;
        else if (i == 3) dp[i] = 5;
        else{
            dp[i] = dp[i-1]+dp[i-2];
            for (int j = 0; j < i-2; j++) dp[i] += 2*dp[j];
        }
    }

    cout << dp[N] << endl;
    return 0;
}

B DAG

これが一番簡単な気がする
辺を逆向きで入れるといいかも
dfsするだけ
$dp[i]$は終点iの時の通り数
計算量は$O(TN)$

#include <bits/stdc++.h>
#include <atcoder/modint>
using namespace std;
using mint = atcoder::modint998244353;

void solve(){
    int N, M;
    cin >> N >> M;
    vector<vector<int>> G(N);
    for (int i = 0; i < M; i++){
        int u, v;
        cin >> u >> v;
        u--, v--;
        G[v].push_back(u);
    }

    vector<bool> vis(N, false);
    vector<mint> dp(N, 0);
    auto dfs = [&](auto& dfs, int v){
        if (vis[v]) return dp[v];
        vis[v] = true;
        if (v == 0) return dp[v] = 1;
        mint res = 0;
        for (int i : G[v]) res += dfs(dfs, i);
        return dp[v] = res;
    };

    cout << dfs(dfs, N-1).val() << endl;
}

int main(){
    int T;
    cin >> T;
    while (T--) solve();
    return 0;
}

C 文字列

簡単目だったけどめんどくさすぎる
$dp[i][a][b][c][j]$=Tのi文字目までの時にAとのLCSの長さがa, BとのLCSの長さがb, CとのLCSの長さがcで最後がj番目のアルファベットの時の通り数
計算量は$O(N|A||B||C|)$

#include <bits/stdc++.h>
#include <atcoder/modint>
using namespace std;
using mint = atcoder::modint998244353;
#define rep(i, N) for(int i = 0; i < N; i++)

int main(){
    int N;
    string A, B, C;
    cin >> N >> A >> B >> C;

    mint dp[N][A.size()+1][B.size()+1][C.size()+1][26];
    rep(i, 26){
        int a = 0, b = 0, c = 0;
        if (A[0] == 'a'+i) a++;
        if (B[0] == 'a'+i) b++;
        if (C[0] == 'a'+i) c++;
        dp[0][a][b][c][i] = 1;
    }

    rep(i, N-1) rep(a, A.size()) rep(b, B.size()) rep(c, C.size()){
        mint bef = 0;
        rep(j, 26) bef += dp[i][a][b][c][j];
        rep(j, 26){
            int na = a, nb = b, nc = c;
            if (A[a] == 'a'+j) na++;
            if (B[b] == 'a'+j) nb++;
            if (C[c] == 'a'+j) nc++;
            dp[i+1][na][nb][nc][j] += bef;
        }
    }

    mint ans = 0;
    rep(a, A.size()) rep(b, B.size()) rep(c, C.size()) rep(i, 26) ans += dp[N-1][a][b][c][i];
    cout << ans.val() << endl;
}

D 紙幣

結構いけた意外と桁DPてきな
dp[i][j]はi桁目まで見た時の最小値
計算量は$O(TN)$

#include <bits/stdc++.h>
using namespace std;
using ll = long long; 
const ll INF = 4e18;

void solve(){
    string S;
    cin >> S;
    reverse(S.begin(), S.end());
    int N = S.size();

    vector<vector<ll>> dp(N+1, vector<ll>(2, INF));
    dp[0][0] = 0;

    for (int i = 0; i < N; i++){
        int n = S[i]-'0';
        for (int j = 0; j <= 1; j++) if (dp[i][j] != INF){
            for (int k = 0; k < 10; k++){
                int v = n+j+k;
                int a = v/10, b = v%10;
                dp[i+1][a] = min(dp[i+1][a], dp[i][j]+k+b);
            }
        }
    }

    cout << min(dp[N][0], dp[N][1]+1) << endl;
}

int main(){
    int T;
    cin >> T;
    while (T--) solve();
    return 0;
}

G 口

これセグ木だな
はい

#include <bits/stdc++.h>
#include <atcoder/segtree>
using namespace std;
using ll = long long; 
const ll INF = 4e18;

struct S{ ll sum, pref, suff, best; };
S e(){ return {0, -INF, -INF, -INF}; }
S op(S a, S b){
    return S{
        a.sum+b.sum,
        max(a.pref, a.sum+b.pref),
        max(b.suff, b.sum+a.suff),
        max({a.best, b.best, a.suff+b.pref})
    };
}

int main(){
    int N, Q;
    ll suma = 0;
    cin >> N >> Q;
    vector<int> A(N);
    atcoder::segtree<S, op, e> seg(N);
    for (int i = 0; i < N; i++){
        cin >> A[i];
        suma += A[i];
        int w = (A[i] == 0? -1: A[i]);
        seg.set(i, S{w, w, w, w});
    }

    while (Q--){
        int i, v;
        cin >> i >> v, i--;
        suma += v-A[i];
        A[i] = v;
        int w = (v == 0? -1: v);
        seg.set(i, {w, w, w, w});
        cout << suma-max(0ll, seg.all_prod().best) << endl;
    }
}

またいつか埋めます
1ってつけときゃいいか