Atcoder Educational DP Contest 題解

HyperSoWeak Lv3
  2024-08-06 18:02:30 2024-08-06 18:02:30 撰寫   2024-12-29 21:16:25 2024-12-29 21:16:25 更新      3.5k 字數  17 分鐘  

我是 dp 菜雞

尚未完成，有時間就會補個題目。巨集們可以在 About 找到，程式碼只放實際有效部分。

Problem A - Frog 1

A - Frog 1

定義 為走到第 個石頭時的最小成本。由於要走到第 階只能從第 或 階，因此轉移式如下

AC code

1
2
3
4
5
6
7
8
9
10
int n, h[100005], dp[100005];

signed main() {
    hyper;
    cin >> n;
    rep1(i,1,n) cin >> h[i];
    dp[1] = 0, dp[2] = abs(h[2] - h[1]);
    rep1(i,3,n) dp[i] = min(dp[i-1]+abs(h[i]-h[i-1]),dp[i-2]+abs(h[i]-h[i-2]));
    cout << dp[n];
}

Problem B - Frog 2

B - Frog 2

定義 為走到第 個石頭時的最小成本。轉移式如下

因為有 種可能，直接跑迴圈轉移即可。

AC code

1
2
3
4
5
6
7
8
9
10
11
12
13
int n, k, h[100005], dp[100005];

signed main() {
    hyper;
    rr(dp,0x3f);
    cin >> n >> k;
    rep1(i,1,n) cin >> h[i];
    dp[1] = 0;
    rep1(i,2,n) rep1(j,1,k) {
        if(i-j >= 0) dp[i] = min(dp[i], dp[i-j]+abs(h[i]-h[i-j]));
    }
    cout << dp[n];
}

Problem C - Vacation

C - Vacation

定義一個二維 dp， 代表考慮第 到 天，且第 天選擇的是活動 。轉移式如下

以此類推。

AC code

1
2
3
4
5
6
7
8
9
10
11
12
13
int n, a[3][MAXN], dp[3][MAXN];

signed main() {
    hyper;
    cin >> n;
    rep1(i,1,n) rep(j,0,3) cin >> a[j][i];
    rep1(i,1,n) {
        dp[0][i] = max(dp[1][i-1]+a[1][i],dp[2][i-1]+a[2][i]);
        dp[1][i] = max(dp[0][i-1]+a[0][i],dp[2][i-1]+a[2][i]);
        dp[2][i] = max(dp[0][i-1]+a[0][i],dp[1][i-1]+a[1][i]);
    }
    cout << max(dp[0][n],max(dp[1][n],dp[2][n]));
}

Problem D - Knapsack 1

D - Knapsack 1

沒有任何變化的 01 背包問題，就不寫題解了嘻嘻。

AC code

1
2
3
4
5
6
7
8
9
10
11
12
13
int n, m, dp[MAXW], w[MAXN], v[MAXN];

signed main() {
    hyper;
    cin >> n >> m;
    rep1(i,1,n) cin >> w[i] >> v[i];
    rep1(i,1,n) {
        for(int j=m; j>=w[i]; --j) {
            dp[j] = max(dp[j], dp[j-w[i]]+v[i]);
        }
    }
    cout << dp[m];
}

Problem E - Knapsack 2

E - Knapsack 2

01 背包問題，但 太大了，所以換個方法定義， 表示要裝總價值 的物品所需的最小容量，然後從價值大到小的開始找答案。

AC code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int n, m, dp[MAXW], w[MAXN], v[MAXN];

signed main() {
    hyper;
    cin >> n >> m;
    rep1(i,1,n) cin >> w[i] >> v[i];
    rr(dp,0x3f);
    dp[0] = 0;
    rep1(i,1,n) {
        for(int j=100000; j>=v[i]; --j) {
            dp[j] = min(dp[j], dp[j-v[i]]+w[i]);
        }
    }
    for(int i=100000; i>=0; --i) {
        if(dp[i] <= m) {
            cout << i;
            return 0;
        }
    }
}

Problem F - LCS

F - LCS

LCS 板子題，dp 時記一下是從誰轉移過來，最後找答案就沿路回推。

AC code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
string s, t;
int dp[3005][3005], pv[3005][3005];

void print(int i, int j) {
    if(i==0 || j==0) return;
    if(pv[i][j]==0) {
        print(i-1, j-1);
        cout << s[i-1];
    }
    else if(pv[i][j]==1) print(i-1, j);
    else print(i, j-1);
}

signed main() {
    hyper;
    cin >> s >> t;
    int ls = s.length(), lt = t.length();
    rep1(i,1,ls) rep1(j,1,lt) {
        if(s[i-1] == t[j-1]) {
            dp[i][j] = dp[i-1][j-1] + 1;
            pv[i][j] = 0;
        }
        else if(dp[i-1][j] >= dp[i][j-1]) {
            dp[i][j] = dp[i-1][j];
            pv[i][j] = 1;
        }
        else {
            dp[i][j] = dp[i][j-1];
            pv[i][j] = 2;
        }
    }
    print(ls, lt);
}

Problem G - Longest Path

G - Longest Path

定義 表示以 為結尾的最長路徑長，並依照拓樸順序遍歷節點 ，如果存在邊 ，就更新

最後答案為

AC code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int n, m, in[MAXN], dp[MAXN];
vector<int> g[MAXN];

signed main() {
    hyper;
    cin >> n >> m;
    rep(i,0,m) {
        int x, y;
        cin >> x >> y;
        g[x].push_back(y);
        in[y]++;
    }
    queue<int> q;
    rep1(i,1,n) if(!in[i]) q.push(i);
    while(!q.empty()) {
        int u = q.front(); q.pop();
        for(int v: g[u]) {
            dp[v] = max(dp[v], dp[u]+1);
            if(!--in[v]) q.push(v);
        }
    }
    cout << *max_element(dp+1, dp+1+n);
}

Problem H - Grid 1

H - Grid 1

經典排組題。走到某一格的方法數就是走到他上面的方法數 + 走到他左邊的方法數，而不能走的格子方法數顯然是 。定義 是走到座標 格子的方法數，轉移式如下

AC code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int h, w, dp[MAXN][MAXN];
string a[MAXN];

signed main() {
    hyper;
    cin >> h >> w;
    rep(i,0,h) cin >> a[i];
    rep(i,0,h) dp[i][0] = 0;
    rep(i,0,w) dp[0][i] = 0;
    dp[1][1] = 1;
    rep1(i,1,h) rep1(j,1,w) {
        if(i==1 && j==1) continue;
        if(a[i-1][j-1] == '#') dp[i][j] = 0;
        else dp[i][j] = (dp[i-1][j] + dp[i][j-1]) % MOD;
    }
    cout << dp[h][w];
}

Problem I - Coins

I - Coins

機率 dp，跟高中數學題差不多。假設 表示有 個硬幣，其中 個是 head 的機率，那麼它可以從 個硬幣推得：

也就是考慮第 個是正面還是反面。注意處理邊界就好，時間複雜度是 。

AC code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int n;
double p[MAXN], dp[MAXN][MAXN];

signed main() {
    hyper;
    cin >> n;
    rep1(i,1,n) cin >> p[i];
    dp[0][0] = 1;
    rep1(i,1,n) {
        dp[i][0] = dp[i-1][0]*(1-p[i]);
        rep1(j,1,i) dp[i][j] = dp[i-1][j-1]*p[i] + dp[i-1][j]*(1-p[i]);
    }
    double sum = 0;
    for(int i=n; i>n-i; --i) sum += dp[n][i];
    cout << fixed << setprecision(10) << sum;
}

Problem J - Sushi

J - Sushi

關鍵是盤子裡最多只會有 3 個壽司，而且因為隨機均勻分布，盤子的順序並不重要，所以我們可以用三個維度 分別表示剩餘 個壽司的盤子數量，空盤子數就是 。令 是盤子在此狀態下時的答案（吃光所需次數的期望值），不難推出：

這邊使用遞迴 + 記憶化搜尋來寫（我也不知道為什麼當初這樣寫，不過這樣不用考慮計算順序），總之複雜度是 稍微有點緊。

AC code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int n, cnt[4];
double dp[MAXN][MAXN][MAXN];

double sol(int x, int y, int z) {
    if(x<0 || y<0 || z<0) return 0;
    if(dp[x][y][z] >= 0) return dp[x][y][z];
    return dp[x][y][z] = (n+x*sol(x-1,y,z)+y*sol(x+1,y-1,z)+z*sol(x,y+1,z-1))/(x+y+z);
}

signed main() {
    hyper;
    cin >> n;
    rep1(i,1,n) {
        int x;
        cin >> x;
        cnt[x]++;
    }
    rep1(i,0,n) rep1(j,0,n) rep1(k,0,n) dp[i][j][k] = -1;
    dp[0][0][0] = 0;
    cout << fixed << setprecision(10) << sol(cnt[1],cnt[2],cnt[3]);
}

Problem K - Stones

K - Stones

一定必勝或必敗，定義 代表目前只有 顆石頭的情況下，先手是否獲勝。只要拿走任一種數量的石頭使得對手接下來必敗就贏了，否則就是輸。轉移式如下

AC code

1
2
3
4
5
6
7
8
9
10
11
12
int n, k, a[105];
bool dp[100005];

signed main() {
    hyper;
    cin >> n >> k;
    rep(i,0,n) cin >> a[i];
    rep1(i,1,k) rep(j,0,n) {
        if(i-a[j] >= 0 && !dp[i-a[j]]) dp[i] = 1;
    }
    cout << (dp[k] ? "First" : "Second");
}

Problem L - Deque

L - Deque

又是賽局的題目，因為兩邊都可以拿東西，所以變成區間 dp。可以看出兩邊都是想讓自己分數越高越好，假設 是 區間中先手減後手的分數最大值（不一定是 或 ），轉移時 會互換，所以變成要找最小值，也就是加負號，得到：

前者表示拿 ，後者表示拿 ，注意 跟 的計算方向是相反的，答案是整個區間，也就是 。

AC code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int n, a[MAXN], dp[MAXN][MAXN];

signed main() {
    hyper;
    cin >> n;
    rep1(i,1,n) {
        cin >> a[i];
        dp[i][i] = a[i];
    }
    for(int l=n; l>=1; --l) {
        rep1(r,l+1,n) {
            dp[l][r] = max(a[l] - dp[l+1][r], a[r] - dp[l][r-1]);
        }
    }
    cout << dp[1][n];
}

Problem M - Candies

M - Candies

設 是考慮到第 個小孩，用掉 個糖果時的方法數，則：

但這樣時間會炸，很容易發現可以用前綴和處理連續區間和，就可以把時間降到 。然後可以用滾動 dp 進一步變成一維空間，好耶。

AC code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int n, k, a[MAXN], dp[MAXK], ps[MAXK];

signed main() {
    hyper;
    cin >> n >> k;
    rep1(i,1,n) cin >> a[i];
    rep1(j,0,k) {
        dp[j] = (j <= a[1]);
        ps[j+1] = ps[j] + dp[j];
    }
    rep1(i,2,n) {
        rep1(j,0,k) dp[j] = (ps[j+1] - ps[max(0,j-a[i])]) % MOD;
        rep1(j,0,k) ps[j+1] = ps[j] + dp[j];
    }
    cout << dp[k];
}

Problem N - Slimes

N - Slimes

典型區間 dp。定義 為合併第 到第 隻史萊姆的最小成本。則轉移式如下

其中 可以用前綴和 處理掉，總複雜度 。

AC code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int n, a[MAXN], dp[MAXN][MAXN], ps[MAXN];

signed main() {
    hyper;
    cin >> n;
    rep1(i,1,n) {
        cin >> a[i];
        dp[i][i] = 0;
        ps[i] = ps[i-1] + a[i];
    }
    rep1(len,2,n) rep1(i,1,n-len+1) {
        int j = i + len - 1;
        dp[i][j] = INF;
        rep(k,i,j) dp[i][j] = min(dp[i][j], dp[i][k]+dp[k+1][j]+ps[j]-ps[i-1]);
    }
    cout << dp[1][n];
}

Problem O - Matching

O - Matching

本質上是二分圖完美匹配數量，用狀壓 dp 可以做。考慮 是前 個男生跟女生子集合 的匹配數，如果 ，代表我可以把 加入 轉移過去，轉移變成：

答案是 ，時間複雜度是 。

可以參考 k 染色问题、二分图完美匹配数、k 路径问题

AC code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int n, dp[22][1<<21];
bool a[21][21];

signed main() {
    hyper;
    cin >> n;
    rep(i,0,n) rep(j,0,n) cin >> a[i][j];
    dp[0][0] = 1;
    rep(i,0,n) rep(t,0,1<<n) {
        if(dp[i][t] == 0) continue;
        rep(j,0,n) if(!(t&(1<<j)) && a[i][j]) {
            dp[i+1][t|(1<<j)] = (dp[i+1][t|(1<<j)] + dp[i][t]) % MOD;
        }
    }
    cout << dp[n][(1<<n)-1];
}

Problem P - Independent Set

P - Independent Set

樹上 dp 題，把節點是黑或白的方法數分開討論，定義 表示節點顏色，是根為 的子樹在 顏色是 時的答案，轉移時就可以分顏色討論，在 dfs 時順便把小孩的答案乘上去，複雜度 。

AC code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
int n, dp[MN][2];
vector<int> e[MN];

void dfs(int u, int p) {
    dp[u][0] = dp[u][1] = 1;
    if(u != 1 && e[u].size() == 1) return;
    for(int v: e[u]) {
        if(v == p) continue;
        dfs(v, u);
        dp[u][0] = (dp[u][0] * (dp[v][0] + dp[v][1])) % MOD;
        dp[u][1] = (dp[u][1] * dp[v][0]) % MOD;
    }
}

signed main() {
    hyper;
    cin >> n;
    rep(i,0,n-1) {
        int x, y;
        cin >> x >> y;
        e[x].push_back(y);
        e[y].push_back(x);
    }
    dfs(1, 0);
    cout << (dp[1][0] + dp[1][1]) % MOD;
}

Problem Q - Flowers

Q - Flowers

看起來是帶權重的 LIS，定義 是選擇的最後一朵是第 朵花的答案，因此只能從高度比目前小的轉移過來，轉移式是：

而答案是 ，但這樣複雜度會變 不會過。我們把高度排序當作 index，就變成單點查詢、區間最大值的問題，簡單用個 BIT（或線段樹）加速就過了，時間複雜度變成 ，好耶。

AC code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
struct Fenwick {
    vector<int> v;
    int sz;
    Fenwick(int n) {
        v.resize(n+1, 0);
        sz = n;
    }
    int lowbit(int x) { return x&-x; }
    void modify(int p, int x) {
        for(int i=p; i<=sz; i+=lowbit(i)) v[i] = max(v[i], x);
    }
    int query(int p) {
        int mx = -INF;
        for(int i=p; i>0; i-=lowbit(i)) mx = max(mx, v[i]);
        return mx;
    }
};

Fenwick bit(MN);

signed main() {
    hyper;
    int n;
    vi h(MN), a(MN);
    cin >> n;
    rep1(i,1,n) cin >> h[i];
    rep1(i,1,n) cin >> a[i];

    vi tmp(h), idx(MN);
    sort(tmp.begin()+1, tmp.begin()+1+n);
    rep1(i,1,n) idx[tmp[i]] = i;

    int ans = -INF;
    rep1(i,1,n) {
        int t = max(bit.query(idx[h[i]]-1), 0) + a[i];
        bit.modify(idx[h[i]], t);
        ans = max(ans, t);
    }
    cout << ans << '\n';
}

Problem R - Walk

R - Walk

這題完全在考矩陣乘法，設 表示從 到 走 步的方法數，則 ，所以用矩陣快速冪算出 然後把所有 entries 相加就是答案ㄌ。時間複雜度是 。

AC code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
mat operator*(const mat &a, const mat &b) {
    int n = a.size();
    mat c(n, vi(n, 0));
    rep(i,0,n) rep(j,0,n) rep(k,0,n)
        c[i][j] = (c[i][j] + a[i][k] * b[k][j]) % MOD;
    return c;
}

mat operator^(mat a, int k) {
    int n = a.size();
    mat b(n, vi(n, 0));
    rep(i,0,n) b[i][i] = 1;
    while(k) {
        if(k & 1) b = b * a;
        a = a * a;
        k >>= 1;
    }
    return b;
}

signed main() {
    hyper;
    int n, k;
    cin >> n >> k;
    mat a(n, vi(n));
    rep(i,0,n) rep(j,0,n) cin >> a[i][j];
    mat b = a ^ k;
    int sum = 0;
    rep(i,0,n) rep(j,0,n) sum = (sum + b[i][j]) % MOD;
    cout << sum << '\n';
}

Problem S - Digit Sum

S - Digit Sum

數位 dp 是我之前沒有碰過的題型，所以看 OI Wiki 研究了一下。

要記錄三個東西，目前位數、總和（取模）、以及前面所有位數是否達到上限（lim）。lim 是一個布林值，舉例來說， 是 ，假設我考慮了前三位是 ，那此時 lim 是 true，表示第四位只能填 ；否則假設前三位是 沒有達到上限，那 lim 就是 false，第四位可以隨便填。

轉移的部分看 code 應該就很清楚了，數位 dp 轉移關係比較複雜，用記憶化搜索比較好寫。記得最後答案要減一因為會把 0 也算進去。

AC code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
string k;
int d, n;
int dp[10005][105][2];

int sol(int pos, int sum, int lim) {
    if(pos == n) return sum == 0;
    int& ret = dp[pos][sum][lim];
    if(~ret) return ret;
    ret = 0;
    int up = lim ? k[pos] - '0' : 9;
    rep1(i,0,up) ret += sol(pos+1, (sum+i)%d, lim&&(i==up));
    return ret %= MOD;
}

signed main() {
    hyper;
    rr(dp, -1);
    cin >> k >> d;
    n = k.size();
    cout << (sol(0, 0, 1) - 1 + MOD) % MOD << '\n';
}

Problem T - Permutation

T - Permutation

這題我覺得有點 tricky，首先最直接想到的是目前處理到的位置跟最後一位數字，這兩個是要記錄的狀態。因此我們定義 是長度 且最後一位為 的方法數（用 的正整數排列）。關鍵在於我們可以從 轉移過來，因為我們可以調整數字，只要不影響大小順序。例如原先是 而第四位想要是 的話，只要把前三位數都 就可以了，也就是變成 。考慮 或 能讓上一個數字是多少，我們可以得到轉移式：

然後簡單用前綴和處理，記得取模。

AC code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
signed main() {
    hyper;
    int n;
    string s;
    cin >> n >> s;
    mat dp(n+1, vi(n+1, 0));
    dp[1][1] = 1;
    rep1(i,2,n) {
        vi ps(i+1, 0);
        rep1(j,1,i-1) ps[j] = (ps[j-1] + dp[i-1][j]) % MOD;
        rep1(j,1,i) {
            if(s[i-2] == '<') dp[i][j] = ps[j-1];
            else dp[i][j] = (ps[i-1] - ps[j-1] + MOD) % MOD;
        }
    }
    int ans = 0;
    rep1(i,1,n) ans = (ans + dp[n][i]) % MOD;
    cout << ans << '\n';
}
  • 標題: Atcoder Educational DP Contest 題解
  • 作者: HyperSoWeak
  • 撰寫于 : 2024-08-06 18:02:30
  • 更新于 : 2024-12-29 21:16:25
  • 連結: https://hypersoweak.github.io/blog/atcoder-educational-dp/
  • 版權宣告: 本作品采用 CC BY-NC-SA 4.0 进行许可。
目錄
Atcoder Educational DP Contest 題解
  1. Problem A - Frog 1
  2. Problem B - Frog 2
  3. Problem C - Vacation
  4. Problem D - Knapsack 1
  5. Problem E - Knapsack 2
  6. Problem F - LCS
  7. Problem G - Longest Path
  8. Problem H - Grid 1
  9. Problem I - Coins
  10. Problem J - Sushi
  11. Problem K - Stones
  12. Problem L - Deque
  13. Problem M - Candies
  14. Problem N - Slimes
  15. Problem O - Matching
  16. Problem P - Independent Set
  17. Problem Q - Flowers
  18. Problem R - Walk
  19. Problem S - Digit Sum
  20. Problem T - Permutation