918-C. The Monster

2021-03-24 20:08:59 +0800 CST Tags: parenthesis-matching

出處：https://codeforces.com/contest/918/problem/C
提交：https://codeforces.com/contest/918/submission/110834112

問題：輸入一個長度介於 $[2,5000]$ 的字串 s，它只包含 ( ) ? 三種符號，而 ? 只可以替換成 ( 或 )，現在我們想統計「最多」有多少個非空子字串可以滿足括號匹配的條件 [1]。所謂最多的意思是，對每次的查詢我們都會隨時讓 ? 替換成最能讓當下欲查詢的子字串滿足括號匹配條件。

解法：
看一下 tags 的分類，就知道這題是古典問題「括號匹配問題」的變形，如果吾人無法在 $\mathcal O(n^2)$ 時間內算出原始不含 ? 之古典版本的字串總共有幾種子字串滿足條件，那麼這題也不會通過。先簡單複習一下古典版本的解法，每次固定一個起始點索引值 i，然後終點索引值 j 從起始點 i 往後迭代到最後 s.length 的過程中隨時統計 s[i:j] 是否滿足條件，方法如下，每次開始一個新的索引值的時候就初始化 counter=0 隨後 s[j] 遇到 ( 的話就做 counter++、遇到 ) 的話就做 counter- -，也就是說過程中一旦遇到 ) 就立馬抓它跟左邊還沒匹配到的 ( 進行匹配並把這一對 ( ) 從字串中抽掉，所以說這個 counter 的意思就是當前進行匹配完畢之後還留下來沒有和 ) 匹配到的 ( 括號的數量，那麼一旦 counter==0 代表當前 s[i:j] 的所有括號都匹配完畢於是必須納入統計，而一旦 counter<0 代表當前有多出來的 ) 無法與 ( 匹配而且後續再遇到 ( 也於事無補所以必須即刻停止統計，最後得到的個數就是答案。

那麼現在含有 ? 的字串問題變形又該怎麼使用 counter 解法呢？先講答案，我們可以多維護一個 question 變數記錄過程中遇到的 ? 數量，特別的是，當 question > counter 的時候，因為會有全部的 ? 都被替換成 ) 而使得至少有一個 ) 無法與足夠量的 ( 匹配的狀況出現，此時我們要自動讓 question- - 和 counter++，也就是強迫讓最新一個 ? 替換成 (，那麼一旦 question==counter 我們便能斷定這個時候的 s[i:j] 必定可以滿足括號匹配條件。古典問題的解法證明還算容易理解，但是變形解法的證明就沒有那麼直觀了，有興趣的讀者可以參考以下。

證明：
在開始證明變形問題的 counter method 會成立之前，必須先理解透徹古典問題的證明方式才行，於是這一段先讓我們來探討為什麼古典問題的解法確實會 work。已知 counter 的意義為從起始索引值開始，截至目前所遇到的 ( 與 ) 的數量差，那由於匹配的必要條件是兩種括號數量相等，所以任意時刻中只要 counter 不為 0 必定無法滿足匹配，而一旦遇到 counter < 0 由於這個時候 ) 多於 (，那麼勢必有多餘的 ) 無法與左邊的 ( 順利匹配，而且再加上任意長度的後綴也不改變此事實，所以遇到這個條件之後可以立刻終止迭代，換言之，還沒終止的時候代表過程中永遠 counter $\ge$ 0，那麼為什麼 counter==0 的時候就能保證匹配呢？要解釋這件事我們只能回憶一下小時候學到的 stack 資料結構，它在遇到 ) 的時候會直接把 stack 內還沒匹配到的 ( 括號 pop 出去，所以 counter 可以視為任意時刻 stack 內還沒匹配到的 ( 數量，於是 counter==0 就直接隱含順利匹配這件事，於是充分條件成立。總結來說，從起始索引值開始到目前的子字串滿足括號匹配條件「若且唯若」過程中的 ( 與 ) 數量差 counter 恆不為負數，而且此時的 ( 與 ) 數量相等。我們現在故意把充要條件寫成這樣的另外一個用意是，因為變形版本問題的 ? 是無法立刻轉換為 ( 或 ) 的，如果再次把 counter 視為 stack 內還沒匹配到的 ( 數量可能就會像我一樣有理解障礙。

回顧一下古典演算法跟變形演算法的差別，後者除了多了 question 變數之外，還多了一條規則就是，當 ( 與 ) 數量差 counter 小於 ? 數量時，立刻將目前為止所遇到的最新一個 ? 替換成 (，其餘規則不變。首先我們知道，新規則會使得從起始索引值開始迭代到發生 counter<0 之前的任意前綴都滿足 counter $\ge$ question $\ge$ 0，但這論述其實還不夠，因為遇到 counter < question 並將最新一個 ? 自動修正為 ( 後，從那個 ? 開始往後到當前字元的恆不等式可能就會破功，所以我們必須重新檢查那個區間。未修改前的區間 s[i:j] 只可能以 ) 或 ? 作結尾，因為只有 ) 能遞減 counter、只有 ? 能遞增 question，使得 counter==question 變成 counter < question。先觀察以 ) 為結尾的區間 s[i:j] = ?…)，它去頭去尾的子字串必定不包含 ? $\not\in$ s[i+1:j-1] 因為我們只能修改所有遇過的 ? 裡面最新一次的那一個；首先觀察替換前對於 s[i:j] 的每個字元，恆有 question $\ge$ 1，那麼替換後很自然地恆有 question $\ge$ 0；接著觀察在替換前對於 s[i:j-1] 的每個字元，恆有 counter $\ge$ question，那麼替換後也很自然地恆有 counter $\gt$ question；最後我們觀察到替換前的 s[j] 必有 counter == question-1，替換後也很自然有 counter $\gt$ question；於是替換後的新區間 s'[i:j] = (…) 的每個字元都滿足 counter $\gt$ question $\ge$ 0。再觀察以 ? 為結尾的區間 s[i:j] = ? 它就只有一個字元，替換前應恆有 counter == question-1 $\ge$ 0，那麼替換後也應有 counter $\gt$ question $\ge$ 0。所以綜上所述，從起始的索引值開始迭代到發生 counter<0 之前的任意前綴「在指定的 ? 皆已替換為 ( 之後」也都滿足 counter $\ge$ question $\ge$ 0。

順著這個條件下去分析，在發生 counter<0 之前如果 counter $\gt$ question，那就算把所有的 ? 換成 ) 左括號與右括號的數量也不可能相等違反必要條件，不可能匹配；如果 counter==question，此時把所有的 ? 換成 ) 的話左括號與右括號一定一樣多，滿足必要條件，更重要的是我們可以直接套證明第一段的底線部分，故充分條件也成立，此時必定滿足匹配條件！最後讓我們來說明為什麼遇到 counter<0 就能斷定此時與之後的子字串都不可能匹配成功，因為根據底線敘述前一刻仍然必須遵守 counter $\ge$ question $\ge$ 0，如果此時 counter<0 (間接隱含 counter==-1)，那麼前一刻的 counter==0 (亦間接隱含 question==0)，換句話說現在並沒有任何 ? 可以消化多餘的 )，這個現象加上任意長度的後綴也不會改變，因此不可能滿足匹配條件，而且程序可以終止！

附註：
[1] 滿足括號匹配的條件有三種：空字串本就滿足括號匹配，滿足括號匹配的字串外圍被 ( ) 包住之後亦滿足括號匹配、兩個滿足括號匹配的字串連接起來亦滿足括號匹配。

實作：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

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

int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); // IO 優化
    int ans = 0;
    string s; cin >> s;
    for (int i=0; i+1<s.length(); i++) {
        int remainedOpen=0, question=0;
        for (int j=i; j<s.length(); j++) {
            if (s[j] == '(') remainedOpen++;
            if (s[j] == '?') question++;
            if (s[j] == ')') remainedOpen--;
            if (remainedOpen < 0) break;
            if (remainedOpen < question) {
                remainedOpen++;
                question--;
            }
            ans += question == remainedOpen;
        }
    }
    cout << ans;
    return 0;
}

結果：