Atcoder DP Contest -- Finished

Created2021-01-24Updated2021-01-24

題單連結

從我一開始打競程就知道這份題單了，但一直忘記要把它清掉
總之今天有空總算是把它清掉了

第一個AC和最後一個AC隔了快一年半= =

既然都清掉了，就挑一些個人覺得還不錯的題目打個題解ㄅ

pJ - Sushi

題意

有nn個盤子，第ii盤有aia_i個sushi
每次你會從11到nn等機率的挑選一個數pp，若ap>0a_p > 0則你會吃掉一個sushi
否則你甚麼事都不會做
求出吃完所有sushi的期望次數
(1≤n≤300,1≤ai≤3)(1 \leq n \leq 300, 1 \leq a_i \leq 3)

解法

dp[a][b][c]dp[a][b][c]代表還剩下aa盤1、bb盤2、cc盤3的期望值，這樣可以列出轉移式：

1
2
3
4
if (a) dp[a][b][c] += dp[a - 1][b][c] * a / n;
if (b) dp[a][b][c] += dp[a + 1][b - 1][c] * b / n;
if (c) dp[a][b][c] += dp[a][b + 1][c - 1] * c / n;
dp[a][b][c] = (dp[a][b][c] + 1) * n / (a + b + c);

後面那一步是由期望值恆等式推出來的：
E=E∗(n−a−b−c)+Eother+1E = E * (n - a - b - c) + E_{other} + 1
E(a+b+c)n=Eother+1\frac{E(a + b + c)}{n} = E_{other} + 1

最後答案當然就是dp[cnt1][cnt2][cnt3]dp[cnt1][cnt2][cnt3]，複雜度O(n3)\mathcal{O}(n^3)

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
41
42
43
44
45
46
47
48
49
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define test(x) cout << "Line(" << __LINE__ << ") " #x << ' ' << x << endl;
#define printv(x) {\
	for (auto i : x) cout << i << ' ';\
	cout << endl;\
}
#define pii pair <int, int>
#define pll pair <lli, lli>
#define X first
#define Y second
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
template<typename A, typename B>
ostream& operator << (ostream& o, pair<A, B> a){
    return o << a.X << ' ' << a.Y;
}
template<typename A, typename B>
istream& operator >> (istream& o, pair<A, B> &a){
    return o >> a.X >> a.Y;
}
const int mod = 998244353, abc = 864197532, N = 100087, logN = 17, K = 333;

double dp[301][301][301];
bool vis[301][301][301];

int main () {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    int cnt[3] = {0, 0, 0};
    for (int i = 0, x; i < n; ++i) cin >> x, cnt[--x]++;
    vis[0][0][0] = true;
    function <double(int, int, int)> solve = [&](int a, int b, int c) {
        if (vis[a][b][c]) return dp[a][b][c];
        if (a) dp[a][b][c] += solve(a - 1, b, c) * a / n;
        if (b) dp[a][b][c] += solve(a + 1, b - 1, c) * b / n;
        if (c) dp[a][b][c] += solve(a, b + 1, c - 1) * c / n;
        vis[a][b][c] = true;
        dp[a][b][c] = (dp[a][b][c] + 1) * n / (a + b + c);
        return dp[a][b][c];
    };
    cout << fixed << setprecision(15) << solve(cnt[0], cnt[1], cnt[2]) << endl;
}

pL - Deque

題意

有一個長度為nn的deque，兩個人輪流進行操作
每次操作可將陣列前面或後面的數移除並加到自己的分數
問雙方都optimal的情況下，先手和後手的分數差距是甚麼
(1≤n≤3000)(1 \leq n \leq 3000)

解法

因為移除的是一段前綴和後綴，所以遊戲中一定會剩一段區間
dp[l][r]dp[l][r]代表剩下區間[l,r)[l, r)，先手方的最大答案
則dp[l][r]=dp[l][r] =
挑前面：a[l]+∑i=l+1i<rai−dp[l+1][r]a[l] + \sum_{i = l + 1}^{i < r}{a_i} - dp[l + 1][r]
挑後面：a[r−1]+∑i=li<r−1ai−dp[l][r−1]a[r - 1] + \sum_{i = l}^{i < r - 1}{a_i} - dp[l][r - 1]
取max

可以使用前綴和O(1)\mathcal{O}(1)轉移，總複雜度O(n2)\mathcal{O}(n^2)

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
41
42
43
44
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define test(x) cout << "Line(" << __LINE__ << ") " #x << ' ' << x << endl;
#define printv(x) {\
	for (auto i : x) cout << i << ' ';\
	cout << endl;\
}
#define pii pair <int, int>
#define pll pair <lli, lli>
#define X first
#define Y second
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
template<typename A, typename B>
ostream& operator << (ostream& o, pair<A, B> a){
    return o << a.X << ' ' << a.Y;
}
template<typename A, typename B>
istream& operator >> (istream& o, pair<A, B> &a){
    return o >> a.X >> a.Y;
}
const int mod = 998244353, abc = 864197532, N = 100087, logN = 17, K = 333;

lli dp[3001][3001];

int main () {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    vector <lli> a(n), pre(n + 1, 0);
    for (int i = 0; i < n; ++i) cin >> a[i], pre[i + 1] = pre[i] + a[i];
    for (int d = 1; d <= n; ++d) {
        for (int i = 0; i + d <= n; ++i) {
            int j = i + d;
            dp[i][j] = max(a[i] + pre[j] - pre[i + 1] - dp[i + 1][j], a[j - 1] + pre[j - 1] - pre[i] - dp[i][j - 1]);
        }
    }
    cout << dp[0][n] - (pre[n] - dp[0][n]) << endl;
}

pO - Matching

題意

有一個nn乘nn的01矩陣aa，問有幾個長度為nn的permutation pp滿足：
∀1≤i≤n,a[i][p[i]]=1\forall 1 \leq i \leq n, a[i][p[i]] = 1
(1≤n≤21)(1 \leq n \leq 21)

解法

dp[s]dp[s]代表考慮ss這個子集的答案
則轉移式：

1
2
3
4
int k = __builtin_popcount(s) - 1;
for (int i = 0; i < n; ++i) if (s & (1 << i)) {
    dp[s] += dp[s ^ (1 << i)] * a[i][k];
}

最後答案會是dp[2n−1]dp[2^{n} - 1]，總複雜度O(n2n)\mathcal{O}(n2^n)

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
41
42
43
44
45
46
47
48
49
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define test(x) cout << "Line(" << __LINE__ << ") " #x << ' ' << x << endl;
#define printv(x) {\
	for (auto i : x) cout << i << ' ';\
	cout << endl;\
}
#define pii pair <int, int>
#define pll pair <lli, lli>
#define X first
#define Y second
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
template<typename A, typename B>
ostream& operator << (ostream& o, pair<A, B> a){
    return o << a.X << ' ' << a.Y;
}
template<typename A, typename B>
istream& operator >> (istream& o, pair<A, B> &a){
    return o >> a.X >> a.Y;
}
const int mod = 1e9 + 7, abc = 864197532, N = 100087, logN = 17, K = 333;

int main () {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    vector <vector <int>> a(n, vector <int>(n));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> a[i][j];
        }
    }
    vector <int> dp(1 << n, 0);
    dp[0] = 1;
    for (int s = 1; s < 1 << n; ++s) {
        int k = __builtin_popcount(s);
        for (int i = 0; i < n; ++i) if (s & (1 << i)) {
            dp[s] += dp[s ^ (1 << i)] * a[i][k - 1];
            if (dp[s] >= mod) dp[s] -= mod;
        }
    }
    cout << dp[(1 << n) - 1] << endl;
}

pT - Permutation

題意

給定nn和一個長度為n−1n - 1的大於小於字串ss，問有幾個長度為nn個permutation pp滿足：
∀1≤i≤n−1\forall 1 \leq i \leq n - 1，p[i]p[i]與p[i+1]p[i + 1]的大小關係為s[i]s[i]
(1≤n≤3000)(1 \leq n \leq 3000)

解法

dp[i][j]dp[i][j]代表長度為ii的permutation滿足前i−1i - 1個限制，且p[i]=jp[i] = j的方法數
則轉移式：

dp[i][j]={s[i]=>,∑k=jk≤i−1dp[i−1][k]s[i]=<,∑k=1k<jdp[i−1][k]dp[i][j] = \begin{cases} s[i] = >, \sum_{k = j}^{k \leq i - 1}{dp[i - 1][k]} \\ s[i] = <, \sum_{k = 1}^{k < j}{dp[i - 1][k]} \end{cases}

可以想成當p[i]=jp[i] = j，那麼就介於jj到i−1i - 1的數值都+1，這樣可以讓陣列還是一個permutation，且大小關係不變
也就是為什麼case1的總和是從jj開始加，而不是j+1j + 1
這樣可以套前綴和O(1)\mathcal{O}(1)轉移，複雜度O(n2)\mathcal{O}(n^2)

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
41
42
43
44
45
46
47
48
49
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define test(x) cout << "Line(" << __LINE__ << ") " #x << ' ' << x << endl;
#define printv(x) {\
	for (auto i : x) cout << i << ' ';\
	cout << endl;\
}
#define pii pair <int, int>
#define pll pair <lli, lli>
#define X first
#define Y second
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
template<typename A, typename B>
ostream& operator << (ostream& o, pair<A, B> a){
    return o << a.X << ' ' << a.Y;
}
template<typename A, typename B>
istream& operator >> (istream& o, pair<A, B> &a){
    return o >> a.X >> a.Y;
}
const int mod = 1e9 + 7, abc = 864197532, N = 1000087, logN = 17, K = 333;

int dp[3001][3001], pre[3002][3002];

int main () {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    string s;
    cin >> n >> s;
    dp[1][1] = 1;
    for (int i = 1; i <= n; ++i) pre[1][i] = 1;
    for (int i = 2; i <= n; ++i) {
        for (int j = 1; j <= i; ++j) {
            if (s[i - 2] == '>') {
                dp[i][j] = (pre[i - 1][i - 1] + mod - pre[i - 1][j - 1]) % mod;
            } else {
                dp[i][j] = pre[i - 1][j - 1];
            }
        }
        for (int j = 1; j <= n; ++j) pre[i][j] = (pre[i][j - 1] + dp[i][j]) % mod;
    }
    cout << pre[n][n] << endl;
}

pW - Intervals

題意

給定nn和mm條規則，每條規則有三個參數l,r,wl, r, w
你要構造出一個長度為nn的01字串，使該字串分數最大，分數的計算方式為：
對於每條操作，若在字串[l,r][l, r]的區間中有至少1個1，則分數會加上ww
問所有可能的分數最大值
(1≤n,m≤2×105,∣ai∣≤109)(1 \leq n, m \leq 2 \times 10^5, |a_i| \leq 10^9)

解法

先講個naiveO(n2)\mathcal{O}(n^2)的解：
dp[i]dp[i]代表考慮前綴ii，且在第ii個位置放11的最大答案，則：
dp[i]=minj<idp[j]+val[j]dp[i] = min_{j < i}{dp[j] + val[j]}
其中val[j]val[j]是完全包含在[j+1,i][j + 1, i]區間內的所有操作權重和

那要如何優化呢？可以發現val陣列的數值會是好幾段區間的總和
所以種一棵區間加值、區間詢問最大值的線段樹
就可以在O(logn)\mathcal{O}(logn)的時間內完成轉移
總複雜度O(nlogn)\mathcal{O}(nlogn)

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define test(x) cout << "Line(" << __LINE__ << ") " #x << ' ' << x << endl;
#define printv(x) {\
	for (auto i : x) cout << i << ' ';\
	cout << endl;\
}
#define pii pair <int, int>
#define pll pair <lli, lli>
#define X first
#define Y second
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
template<typename A, typename B>
ostream& operator << (ostream& o, pair<A, B> a){
    return o << a.X << ' ' << a.Y;
}
template<typename A, typename B>
istream& operator >> (istream& o, pair<A, B> &a){
    return o >> a.X >> a.Y;
}
const int mod = 998244353, abc = 864197532, N = 100087, logN = 17, K = 333;

struct Seg {
    int l, r, m;
    long long val, lz;
    Seg* ch[2];
    Seg (int _l, int _r) : l(_l), r(_r), m(l + r >> 1) {
        if (r - l > 1) {
            ch[0] = new Seg(l, m);
            ch[1] = new Seg(m, r);
            pull();
        }
        val = lz = 0;
    }
    void pull() {val = max(ch[0]->val, ch[1]->val);}
    void push() {
        if (r - l > 1 && lz) {
            ch[0]->lz += lz;
            ch[0]->val += lz;
            ch[1]->lz += lz;
            ch[1]->val += lz;
        }
        lz = 0;
    }
    void add(int a, int b, long long v) {
        if (a <= l && r <= b) val += v, lz += v;
        else {
            push();
            if (a < m) ch[0]->add(a, b, v);
            if (m < b) ch[1]->add(a, b, v);
            pull();
        }
    }
    long long query(int a, int b) {
        if (a <= l && r <= b) return val;
        push();
        long long ans = -1ll << 60;
        if (a < m) ans = max(ans, ch[0]->query(a, b));
        if (m < b) ans = max(ans, ch[1]->query(a, b));
        return ans;
    }
};

struct op {
    int l, r, w;
};

int main () {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    vector <op> a[n + 2];
    for (int i = 0, l, r, w; i < m; ++i) {
        cin >> l >> r >> w, r++;
        a[l].pb({0, l, w});
        a[r].pb({0, l, -w});
    }
    Seg root(0, n + 1);
    vector <lli> dp(n + 1, 0);
    for (int i = 1; i <= n; ++i) {
        for (op &o : a[i]) {
            root.add(o.l, o.r, o.w);
        }
        dp[i] = root.query(0, i);
        root.add(i, i + 1, dp[i]);
    }
    cout << *max_element(all(dp)) << endl;
}

pX - Tower

題意

有nn個方塊，每個方塊有數值w,s,vw, s, v
現在要把這些方塊疊成一座塔，須滿足以下限制：
每一個方塊上方的方塊的ww總和需≤\leq該方塊的ss值

一座塔的價值定義為所有方塊vv的總和，求所有可能的塔權重最大值

解法

首先我們要先將方塊排序好，使我們按照順序取，直接疊上去會是最優
假設現在有兩個方塊數值為s1,w1,s2,w2s1, w1, s2, w2
須使剩下的ss值越大越好(這樣才有機會放更多東西)
因此：若1要排在2下面，需滿足：
min(s1−w2,s2)>min(s2−w1,s1)min(s1 - w2, s2) > min(s2 - w1, s1)
s1−w2>s2−w1s1 - w2 > s2 - w1 (原因：s1,s2s1, s2絕對不會是最小值)
s1+w1>s2+w2s1 + w1 > s2 + w2
所以只要按照w+sw + s的順序排序好一定會是最優的

再來就單純了，dp[i][j]dp[i][j]代表考慮前ii個方塊，還剩下jj空間的答案
轉移式：dp[i][min(j−w,s)]=max(dp[i−1][j]+v,dp[i−1][min(j−w,s)])dp[i][min(j - w, s)] = max(dp[i - 1][j] + v, dp[i - 1][min(j - w, s)])

答案會是dp[n−1]dp[n - 1]的最大值，複雜度O(C∗n)\mathcal{O}(C * n)，CC是值域

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
41
42
43
44
45
46
47
48
49
50
51
52
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define test(x) cout << "Line(" << __LINE__ << ") " #x << ' ' << x << endl;
#define printv(x) {\
	for (auto i : x) cout << i << ' ';\
	cout << endl;\
}
#define pii pair <int, int>
#define pll pair <lli, lli>
#define X first
#define Y second
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
template<typename A, typename B>
ostream& operator << (ostream& o, pair<A, B> a){
    return o << a.X << ' ' << a.Y;
}
template<typename A, typename B>
istream& operator >> (istream& o, pair<A, B> &a){
    return o >> a.X >> a.Y;
}
const int mod = 998244353, abc = 864197532, N = 100087, logN = 17, K = 333;

struct tower {
    int w, s, v;
    bool operator < (const tower& o) const {
        return w + s > o.w + o.s;
    }
};

int main () {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    vector <tower> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i].w >> a[i].s >> a[i].v;
    sort(all(a));
    vector <lli> pre(20001, 0), dp;
    for (tower &t : a) {
        dp = pre;
        for (int i = 20000; i >= t.w; --i) {
            dp[min(i - t.w, t.s)] = max(dp[min(i - t.w, t.s)], pre[i] + t.v);
        }
        swap(pre, dp);
    }
    cout << *max_element(all(pre)) << endl;
}