918-D. MADMAX

2021-03-26 20:16:31 +0800 CST Tags: dp, game-theory

出處：https://codeforces.com/contest/918/problem/D
提交：https://codeforces.com/contest/918/submission/110970920

問題：給定 $n\in[2,100]$ 個頂點以及 m 條從 v 到 u 並且標有一個英文小寫字母 c 的有向邊，每條邊都不會指向自己，每對頂點之間至多只會有一條邊，整張圖也不會有環。定義遊戲規則如下：每次先手後手會各自站在一個頂點上 (可以重疊)，先手必須選一條邊走到下一個頂點，假設這條邊的字母是 c，那麼此時後手變先手，他/她也要繼續選一條邊走到下一個頂點，但是這條邊的字母就必須不小於 c，遊戲進行到最後沒路走的人就輸了。請問當先手跟後手的起始點分別散佈在不同頂點的時候誰會贏？

解法：這題也是典型的遊戲理論，它有趣的地方在於 state 的設計，官方解答給的定義是 dfs(u, v, c) 代表先手站在 u、後手站在 v，此時可行邊的字母必須不小於 c 的時候，如果先手會贏則為 true，後手會贏則為 false。吾人易知它的遞迴算法為：如果存在一條標有字母 c' $\ge$ c 的邊 u $\rightarrow$ u$_0$ 使得 dfs(v, u$_0$, c') 是為 false，這意味著先手可以選擇這條邊讓後手必敗，使得 dfs(u, v, c) 是為 true；反之如果不存在這樣子的一條邊，那 dfs(u, v, c) 就只能是 false 了。除了遞迴函式的寫法之外，DP 的設計也很巧妙，這題還有一個很重要的特性是，若 dfs(u, v, c) 是 true，那麼所有對於 c' $\le$ c 的 dfs(u, v, c') 也勢必是為 true；如果 dfs(u, v, c) 是 false，那麼所有對於 c' $\ge$ c 的 dfs(u, v, c') 也勢必是為 false，所以我 dp[u][v][c] 的第三個 entry 其實用不到 26 個字元，只要維護兩個數字分別是結果為 true 的上界和結果為 false 的下界即可。

實作：

 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


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

int n, m, a, b;
char c, dp[101][101][2];
vector<pair<int, int>> adj[101];

bool dfs(int u, int v, int c) {
    if (dp[u][v][0] && c<=dp[u][v][0]) return true;
    if (dp[u][v][1] && dp[u][v][1]<=c) return false;
    bool ans = false;
    for (auto &pii: adj[u]) {
        if (pii.second >= c)
            ans |= !dfs(v, pii.first, pii.second);
    }
    if (ans && (!dp[u][v][0] || c>dp[u][v][0])) dp[u][v][0] = c;
    if (!ans && (!dp[u][v][1] || c<dp[u][v][1])) dp[u][v][1] = c;
    return ans;
}

int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); // IO 優化
    cin >> n >> m;
    for (int i=0; i<m; i++) {
        cin >> a >> b >> c;
        adj[a].push_back(pair<int, int>(b, c-'a'+1));
    }
    for (int i=1; i<=n; i++) {
        for (int j=1; j<=n; j++)
            cout << char('B' - dfs(i, j, 1));
        cout << '\n';
    }
    return 0;
}

結果： Example image