779-D. String Game

2021-03-21 12:24:30 +0800 CST Tags: binary search, sequence

出處：https://codeforces.com/contest/779/problem/D
提交：https://codeforces.com/contest/779/submission/110580384

問題：給定一個大字串 t 和小字串 p，其中 $1\le|p|\lt|t|\le200000$，接著有 |t| 個整數分別代表每次要從字串 t 抹除的字元 index (抹除後其他字元的 index 不變)，請問至多可以抹除幾個字元使得 p 仍然是剩下的字串 t' 的子序列 (subsequence)？

解法：這題難倒我的點還是一樣因為不容易想到 binary search，因為看到子序列的題目你會很容易地往 DP 的解法去想，所以在經歷這題之後我就更有系統性地把 binary search 的適用時機整理好並記錄下來，其實就是對抹除的字元數量 m 作二分搜。那這題還有一個實作小技巧就是抹除過後的字元就不會再度出現，所以我們可以用一個陣列 en 記錄每個字元在第幾次抹除之後就不可使用 (disabled)；至於檢查子序列的部分就沒什麼可以加速的地方，就是一般地線性時間從左掃到右而已。題外話一下，我在猜如果不使用實作小技巧，意即讓整數陣列 en 退化成布林陣列，每次更新 m 之後都重新記錄哪些字元才是 disabled，這個時間其實跟檢查子序列一樣都是線性的，所以理論上應該也是要會過。

實作：

 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


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

string t, p;
int en[200000];

bool match(int m) {
    int ti = 0;
    for (int pi=0; pi<p.length(); pi++, ti++)
        while (ti<t.length() && !((en[ti]==0 || en[ti]>m) && p[pi]==t[ti])) ti++;
    return ti <= t.length(); // mismatch iff "ti > t.length()"
}

int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); // IO 優化
    cin >> t >> p; // t 大 p 小
    for (int i=0; i<t.length(); i++) {
        int x; cin >> x; x--;
        en[x] = i+1; // if en[x]>0 then t[x] is disabled when m>=en[x].
    }
    int lb=0, ub=t.length()-1, ans;
    while (lb <= ub) {
        int m = (lb + ub) / 2;
        if (match(m)) {
            ans = m;
            lb = m + 1;
        } else
            ub = m - 1;
    }
    cout << ans;
    return 0;
}

結果： Example image