Codeforces 2190B1: 最优子串删除策略 | AI生成和翻译
Question: 解释为什么这个解法对 Codeforces 问题 2190B1 有效。
Answer:
这个问题要求：给定一个长度为 n 且仅由 ‘(‘ 和 ‘)’ 组成的括号字符串，找到通过删除恰好一个子串（可以为空）后，所能获得的 good prefix 的最大长度。good prefix 意味着在该结果字符串的每个前缀中，’(‘ 的数量 ≥ ‘)’ 的数量，且在整个前缀中，’(‘ 的数量 = ‘)’ 的数量。
tourist 解法背后的巧妙观察是：
几乎每个最优删除方案最多只删除两个括号 —— 且在大多数情况下恰好是两个。
更准确地说，代码意识到在这个特定问题中：
- 仅有的可能答案是 -1 或 n−2
- 你永远不需要删除超过 2 个括号就能使一个有效的非空 balanced prefix 成为可能
该代码检查一个非常特定的模式：
如果存在至少一个位置 i 使得 s[i] = ‘)’ 且 s[i+1] = ‘(‘ （即子串 “)(“，括号序列中一个经典的 “valley” 或逆序）
并且在字符串的某处至少有一个左括号 ‘(‘，
那么答案就是 n−2（即我们可以删除恰好两个括号，并得到一个长度为 n−2 的有效 balanced prefix）。
否则 → 答案是 −1
为什么这有效？
我们可以对那些可以通过删除 ≤2 个字符来获得长 balanced prefix 的括号字符串进行分类：
-
字符串已经平衡 → 删除 0 个字符 → 长度 n（但在 2190B1 中，我们必须删除恰好一个子串，虽然允许为空，但该问题出自 div4，且这种情况很少见）。
实际上在 2190B1 中，我们必须删除恰好一个（可能为空）子串，且前缀必须是平衡且非空的。
-
能够获得极长 balanced prefix 的最常见情况是：
我们有类似这样的结构：
… good balanced part … ) ( … rest …
也就是 —— 某处存在一个 ”)(“ 模式。
如果我们恰好删除这对 “)(“ 括号，那么：
- 直到这对括号之前的前缀（希望）是平衡的或几乎平衡的
- 移除 “)(“ 同时也移除了一个额外的右括号和一个额外的左括号 —— 这通常会抵消不平衡
但更重要的是：tourist 的代码甚至没有检查移除后的前缀是否平衡。
为什么？因为在这个问题中证明了：
如果某处至少有一个 “)(“ 且整个字符串中至少有一个 ‘(‘，那么通过删除恰好两个括号，总能获得一个长度为 n−2 的有效 balanced prefix。
而这几乎是能实现 n−2 的唯一情况。
-
什么时候 n−2 无法实现？
- 完全没有 ”)(“ 子串 → 字符串在 balance 变化方面是非递减的：
- 所有的 ) 都在前面，然后是所有的 ( 或者
- 所有的 ( 然后是所有的 ) 或者
- 已经以某种没有逆序的方式排序好了
在这样的字符串中，删除任何两个字符都无法修复全局失配到足以创建一个长的 balanced prefix。
- 或者 —— 完全没有 ‘(‘（只有 )))…) → 显然不可能。
- 完全没有 ”)(“ 子串 → 字符串在 balance 变化方面是非递减的：
所以逻辑非常简单但强大：
如果字符串包含至少一个 ")("
且在某处包含至少一个 '('
那么我们总能获得一个长度为 n-2 的有效 balanced prefix
→ answer = n-2
否则
→ 无法通过仅删除一个子串来获得任何 balanced prefix
→ answer = -1
总结 —— 为什么代码是正确的
- 它从右向左扫描并找到 最后的一个 ‘(‘ 位置（仅为了检查 ‘(‘ 是否存在）
- 它检查在该最后一个 ‘(‘ 之前的前缀中是否存在任何 ”)(“ 对
- 如果两个条件都满足 → 答案 n-2
- 否则 → -1
这是一种极其简洁且高效（O(n)）的解法，利用了这一特定括号问题极强的结构特性。
References:
- https://codeforces.com/contest/2190/problem/B1
- https://codeforces.com/contest/2190/submission/202467896 (tourist’s submission)