病毒演化 題解｜APCS 2020 年 7 月高級 第 4 題

前置知識

這題是樹上的動態規劃，每個節點只有四種狀態，下面的講解直接把這些當成已知，沒讀過的先讀；同一個主題兩邊都有的，對照著讀會更快上手：

  • 樹、把孩子的結果交給父親：NTUCPC Guide〈樹〉——「子樹大小」那段的寫法；NTUCPC Guide〈樹的應用〉最後的「樹上匹配問題」示範了同一招怎麼用在最佳化問題上：先把每個孩子的子樹解決掉，再想「父親怎麼跟孩子的答案合併」。
  • 狀態不只一個維度的 DP：NTUCPC Guide〈多個維度的 DP〉——「\(dp[i][j]\) ＝ 第 \(i\) 個做了第 \(j\) 種選擇」這種設計；本題每個病毒的 \(j\) 就是它這個位置選了哪個字元。吳邦一《AP325》第 8 章的習題 Q-8-16 就是本題（教材 PDF 第 323～325 頁），提示寫到「對每個節點算四個成本」。
  • string：用 s[pos] 取第 pos 個字元就夠。

簡潔題意

\(n\) 種病毒構成一棵樹（編號 \(i\) 由編號 \(j\) 演化而來；\(i = j\) 的是根，恰有一個）。每種病毒有一條長度 \(m\) 的 RNA 序列，字元是 A、U、C、G 或未知的 @，每個 @ 可以各自換成四種字元之一。把所有 @ 決定好之後，每條邊（病毒與它的來源）的距離是兩條序列不同的位置數，求所有邊的距離總和最小是多少（\(1 \le n \le 1000\)，\(1 \le m \le 80\)）。

依正確通過的測試資料筆數給分，其中：

  • 子題組 1（\(20\) 分）：序列裡沒有 @，且每個非根病毒都滿足 \(j < i\)。
  • 子題組 2（\(40\) 分）：每個非根病毒都滿足 \(j < i\)。
  • 子題組 3（\(40\) 分）：無額外限制。

先拿下 20 分：沒有 @ 就直接數

沒有 @ 時什麼都不用決定，答案就是每條邊逐位置比對、數不同的位置數。讀入時把第 \(i\) 行存成 parent[i]、rna[i]（編號是任意的，用編號當索引存，不要用讀入的順序），再對每個非根病毒 \(v\) 比 rna[v] 和 rna[parent[v]]。

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

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> parent(n + 1);
    vector<string> rna(n + 1);
    for (int k = 0; k < n; k++) {
        int i, j;
        string s;
        cin >> i >> j >> s;
        parent[i] = j;
        rna[i] = s;
    }
    int answer = 0;
    for (int v = 1; v <= n; v++) {
        if (parent[v] == v) continue;                    // 最原始的病毒沒有來源
        for (int pos = 0; pos < m; pos++)
            if (rna[v][pos] != rna[parent[v]][pos]) answer++;
    }
    cout << answer << '\n';
    return 0;
}

有 @ 的範例這份程式會把 @ 當成一個跟誰都不同的字元，範例 1 印 2、範例 2 印 4 是正常的；子題組 1 的 \(20\) 分穩穩到手。

關鍵觀察：每個位置獨立，一個位置只有四種可能

距離是「不同的位置數」，第 \(1\) 個位置怎麼選完全不影響第 \(2\) 個位置的距離。所以把問題拆成 \(m\) 個互不相干的小問題：只看序列的第 \(pos\) 個字元，決定每個 @ 要變成什麼，讓這個位置上所有邊的距離總和最小；\(m\) 個位置各算一次再相加。

固定一個位置之後，每個病毒只有四種可能的字元。對病毒 \(v\) 定義四個數：cost[v][c] ＝ 把 \(v\) 在這個位置固定成字元 \(c\) 時，\(v\) 的子樹內部（\(v\) 到孩子、孩子到孫子……）的距離總和最小是多少。\(v\) 本來就是固定字元的話，只有那一格是 \(0\)，其他三格設成「不可能」（用一個很大的數 \(\infty\)）；\(v\) 是 @ 的話，四格一開始都是 \(0\)。

把孩子 \(u\) 併進父親 \(v\) 時，對父親的每一格 \(c\)：孩子可以也選 \(c\)（這條邊距離 \(0\)，付 cost[u][c]），或選別的字元 \(d\)（這條邊距離 \(1\)，付 cost[u][d] + 1）。孩子選別的字元時當然挑最便宜的，所以

\[\text{cost}[v][c] \mathrel{+}= \min\bigl(\text{cost}[u][c],\ \min_d \text{cost}[u][d] + 1\bigr)\]

每個孩子各加一次。四格的最小值一算，「同字元免費、換字元付 \(1\)」就是全部的規則。全部併完之後，根的四格取最小就是這個位置的答案。圖 1 是範例 2 的完整計算：病毒 2 是 @，底下兩個 A 讓它固定成 A 最便宜（\(0\)）；根也是 @，固定成 C 時只有病毒 2 要換（\(1\)），固定成 A 時病毒 3、4 都要換（\(2\)），答案 \(1\)。

圖 1：範例 2 每個病毒的 cost 表（固定成 A、U、C、G 時子樹內的最少變異數），根的四格最小值 1 就是答案

從 20 分到 60 分：父親編號比較小，倒著掃編號就是正確順序

要算 cost[v] 必須先把 \(v\) 的每個孩子算完。子題組 1、2 保證每個非根病毒的來源編號比自己小，也就是子孫的編號都比祖先大，所以從 \(v = n\) 倒著掃到 \(1\)，處理到 \(v\) 時它的所有子孫都已經併好了，直接把 \(v\) 的四格併進 parent[v] 即可，連樹的孩子串列都不用建。

cost 開成一個長度 \((n + 1) \times m\) 的 vector，每格是四個整數的 array，病毒 \(v\) 的第 \(pos\) 個位置放在 cost[v * m + pos]。

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

const int INF = 1000000000;
int letterId(char c) {                                   // A U C G → 0 1 2 3；@ → -1
    if (c == 'A') return 0;
    if (c == 'U') return 1;
    if (c == 'C') return 2;
    if (c == 'G') return 3;
    return -1;
}

int n, m;
vector<int> parent;
vector<string> rna;
vector<array<int, 4>> cost;                              // cost[v * m + pos][c]

int main() {
    cin >> n >> m;
    parent.assign(n + 1, 0);
    rna.assign(n + 1, "");
    for (int k = 0; k < n; k++) {
        int i, j;
        string s;
        cin >> i >> j >> s;
        parent[i] = j;
        rna[i] = s;
    }
    cost.assign((n + 1) * m, {0, 0, 0, 0});
    for (int v = 1; v <= n; v++)                         // 起始值：固定字元只有一格是 0，其餘不可能
        for (int pos = 0; pos < m; pos++) {
            int fixed = letterId(rna[v][pos]);
            if (fixed != -1)
                for (int c = 0; c < 4; c++)
                    if (c != fixed) cost[v * m + pos][c] = INF;
        }
    for (int v = n; v >= 1; v--) {                       // 編號大的先處理：子孫編號都比自己大，已經算完
        if (parent[v] == v) continue;
        int u = parent[v];
        for (int pos = 0; pos < m; pos++) {
            array<int, 4> &child = cost[v * m + pos];
            int cheapest = min({child[0], child[1], child[2], child[3]});
            for (int c = 0; c < 4; c++)
                if (cost[u * m + pos][c] < INF)
                    cost[u * m + pos][c] += min(child[c], cheapest + 1);   // 同字元免費；換字元付 1
        }
    }
    int answer = 0;
    for (int v = 1; v <= n; v++)
        if (parent[v] == v)
            for (int pos = 0; pos < m; pos++)
                answer += min({cost[v * m + pos][0], cost[v * m + pos][1], cost[v * m + pos][2], cost[v * m + pos][3]});
    cout << answer << '\n';
    return 0;
}

父親是固定字元時，它的三格 \(\infty\) 不能再加（加了會溢位、也沒意義），所以只對 < INF 的格子加。每條邊、每個位置做常數次運算，\(O(nm)\)。兩個範例的來源編號都比較小，這份程式兩個範例都過；子題組 3 的測資父親編號可能比孩子大，倒著掃會在孩子併進來之前就把父親併走，本站測資掛 \(5\) 筆，\(60\) 分穩穩到手。

從 60 分到 100 分：先從根列出順序，再倒過來走

編號沒有保證時，只要自己造一個「父親在孩子前面」的順序就好：建孩子串列，從根開始像 BFS 一樣往下列（先把根放進 order，再逐個把 order[k] 的孩子接在後面）。order 裡每個病毒都排在自己的子孫前面，把它倒過來走，就跟剛才「編號倒著掃」一模一樣，併的那幾行一個字都不用改。

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

const int INF = 1000000000;
int letterId(char c) {                                   // A U C G → 0 1 2 3；@ → -1
    if (c == 'A') return 0;
    if (c == 'U') return 1;
    if (c == 'C') return 2;
    if (c == 'G') return 3;
    return -1;
}

int n, m;
vector<int> parent;
vector<string> rna;
vector<vector<int>> children;
vector<array<int, 4>> cost;                              // cost[v * m + pos][c]

int main() {
    cin >> n >> m;
    parent.assign(n + 1, 0);
    rna.assign(n + 1, "");
    children.assign(n + 1, {});
    int root = 0;
    for (int k = 0; k < n; k++) {
        int i, j;
        string s;
        cin >> i >> j >> s;
        parent[i] = j;
        rna[i] = s;
        if (i == j) root = i;
        else children[j].push_back(i);
    }
    vector<int> order;                                   // 從根往下列出：每個病毒都排在它的子孫前面
    order.push_back(root);
    for (int k = 0; k < (int)order.size(); k++)
        for (int child : children[order[k]]) order.push_back(child);

    cost.assign((n + 1) * m, {0, 0, 0, 0});
    for (int v = 1; v <= n; v++)
        for (int pos = 0; pos < m; pos++) {
            int fixed = letterId(rna[v][pos]);
            if (fixed != -1)
                for (int c = 0; c < 4; c++)
                    if (c != fixed) cost[v * m + pos][c] = INF;
        }
    for (int k = n - 1; k >= 1; k--) {                   // 把 order 倒過來走：子孫一定比祖先先處理
        int v = order[k], u = parent[v];
        for (int pos = 0; pos < m; pos++) {
            array<int, 4> &child = cost[v * m + pos];
            int cheapest = min({child[0], child[1], child[2], child[3]});
            for (int c = 0; c < 4; c++)
                if (cost[u * m + pos][c] < INF)
                    cost[u * m + pos][c] += min(child[c], cheapest + 1);
        }
    }
    int answer = 0;
    for (int pos = 0; pos < m; pos++)
        answer += min({cost[root * m + pos][0], cost[root * m + pos][1], cost[root * m + pos][2], cost[root * m + pos][3]});
    cout << answer << '\n';
    return 0;
}

\(n = 1000\)、\(m = 80\) 時表格 \(8 \times 10^4\) 格、每格四個數，本站實測最大測資不到 \(0.01\) 秒。答案最大是每條邊每個位置都不同：\((n - 1) \times m = 79920\)，int 綽綽有餘。

測過再交：範例沒有「根不是 1」與「子孫決定祖先」

兩個範例蓋到了「@ 跟著父親」（範例 1）與「@ 跟著多數的孩子」（範例 2）。沒蓋到：根不是編號 \(1\)、父親編號比孩子大、@ 夾在兩個固定字元中間、以及要看孫子才知道父親該選什麼。

輸入 正確輸出 這一筆在測什麼
1 3 ／ 1 1 @A@ 0 只有根：沒有邊，@ 隨便選
2 2 ／ 2 2 AU ／ 1 2 @G 1 根是 \(2\)、父親編號比孩子大：第 1 個位置 @ 選 A 免費，第 2 個位置 G 對 U 一定差 \(1\)
3 1 ／ 1 1 A ／ 2 1 @ ／ 3 2 C 1 @ 夾在 A 與 C 中間：選哪個都只差一條邊
4 1 ／ 1 1 @ ／ 2 1 C ／ 3 1 C ／ 4 1 A 1 根是 @、孩子兩個 C 一個 A：根該選 C；把 @ 一律換成 A 會印 2
4 1 ／ 1 1 A ／ 2 1 @ ／ 3 2 C ／ 4 2 C 1 病毒 2 的 @ 要看孫子：選 C 只有跟父親差 \(1\)，從父親往下照抄 A 會印 2
3 1 ／ 3 3 A ／ 2 3 @ ／ 1 2 C 1 父親編號比孩子大的鏈：倒著掃編號會先把 2 併進 3、再把 1 併進已經併走的 2，印 0
3 2 ／ 1 1 AA ／ 2 1 @@ ／ 3 2 UC 2 兩個位置各自獨立：第 1 個位置差 \(1\)、第 2 個位置差 \(1\)
用程式造：\(n = 1000\)、\(m = 80\)，鏈狀樹（病毒 \(i\) 的來源是 \(i - 1\)），奇數編號全 A、偶數編號全 U 79920 答案最大 \((n - 1) \times m\)：int 裝得下
用程式造：\(n = 1000\)、\(m = 80\)，鏈狀樹，序列全是 @ 0 全部未知：全選同一個字元就是 \(0\)

九筆都親眼看過正確，這題就穩了。

常犯錯誤
  • 把 @ 一律換成同一個字元（例如 A）：範例 1 印 1、範例 2 印 2；本站測資掛 \(11\) 筆。
  • 從根往下走，@ 直接照抄父親的字元：子孫可能讓父親該選別的字元；範例 2 印 2（根選了 A，病毒 3、4 的 C 各付 \(1\)），自測表第 5 列印 2；本站測資掛 \(11\) 筆。
  • 順序寫反：從根往下併（父親先、孩子後）：孩子還沒算完就被併進去，範例 2 印 0。一定要子孫先、祖先後。
  • 子題組 3 還倒著掃編號：父親編號可能比孩子大，範例剛好都是父親比較小所以過了；自測表第 6 列印 0，本站子題組 3 的測資掛 \(5\) 筆。
  • 根的 @ 先隨便固定成一個字元再做 DP：根跟別人一樣要看孩子決定；範例 2 印 2，本站測資掛 \(11\) 筆。
  • 忘了跳過父親是固定字元時的三格 \(\infty\)：把 \(\infty\) 繼續往上加，加到溢位變成負數，答案就會被這些負數帶走。只對 < INF 的格子加。