[codeforces] 1976D. Invertible Bracket Sequences

문제 링크

올바른 괄호 문자열 $s$가 주어집니다. 이때 $l$번째 문자부터 $r$번째 문자까지를 '('는 ')'로, ')'는 '('로 바꿔도 올바른 괄호 문자열이 성립하는 순서쌍 $(l, r)$의 갯수를 구하는 문제입니다.

임의의 괄호 문자열 $t$에 대해서 아래 조건을 만족하는 수열 $b$를 만들어 보겠습니다.

• $b_{0} = 0$
• $t$의 $i$번째 문자가 '('면 $b_{i} = b_{i-1}+1$, ')'면 $b_{i} = b_{i-1}-1$ $(1 \leq i \leq |t|)$

그럼 $t$가 올바른 괄호 문자열인것과 수열 $b$가 아래 조건을 만족하는것은 서로 동치입니다.

• $b_{|t|} = 0$
• $\forall \; 0 \leq i \leq |t| \quad b_{i} \geq 0$

올바른 괄호 문자열을 판별하는 과정을 잘 떠올려보면 위 사실을 어렵지 않게 이해할 수 있습니다.

$s$로부터 나온 수열을 $a$라고 할 때 다음 내용을 증명해 보겠습니다.

Theorem. $(l, r)$이 우리가 구하고자하는 순서쌍을 만족하는것과 수열 $a$가 $a_{r} = a_{l-1}$과 $\max(\{a_{i}\}_{i=l}^r) \leq 2 \cdot a_{l-1}$를 만족하는것은 서로 동치이다.

proof. 설명을 위해 $l$번째부터 $r$번째 까지의 괄호를 바꿔서 만든 문자열에 대한 수열을 $a'$이라고 하겠습니다.

먼저 수열 $a$가 $a_{r} = a_{l-1}$과 $\max(\{a_{i}\}_{i=l}^r) \leq 2 \cdot a_{l-1}$를 만족 한다고 가정해 보겠습니다.

그럼 아래 과정을 통해 $a'_{|s|} = 0$임을 보일 수 있습니다.

또한 아래 과정을 통해 $\forall \; 0 \leq i \leq |s| \quad a'_{i} \geq 0$ 또한 보일 수 있습니다.

즉, 새롭게 만들어지는 문자열 또한 올바른 괄호 문자열이 되므로 $(l, r)$은 우리가 구하고자하는 순서쌍을 만족합니다.

반대로 $(l, r)$이 우리가 구하고자하는 순서쌍을 만족한다고 가정해 보겠습니다.
만약에 $a_{r} = a_{l-1}$을 만족하지 않는다면 $a'_{|s|} \neq 0$이 됩니다. 이는 가정에 모순이므로 귀류법에 의해 $a_{r} = a_{l-1}$을 만족합니다.

만약에 $\max(\{a_{i}\}_{i=l}^r) \leq 2 \cdot a_{l-1}$를 만족하지 않는다면 $\exists \; 0 \leq i \leq |s| \quad a'_{i} < 0$를 만족합니다. 이는 가정에 모순이므로 귀류법에 의해 $\max(\{a_{i}\}_{i=l}^r) \leq 2 \cdot a_{l-1}$를 만족합니다.

이것으로 증명이 완료되었습니다.

즉 수열 $a$에서 $a_{r} = a_{l-1}$과 $\max(\{a_{i}\}_{i=l}^r) \leq 2 \cdot a_{l-1}$를 만족하는 순서쌍 $(l, r)$의 갯수를 구하면 우리가 원하는 순서쌍의 갯수를 구할 수 있습니다.

그럼 순서쌍의 갯수를 어떻게 구할 수 있을까요? 간단하게 $a_{r} = a_{r-1} = 1$인 경우만 생각해보겠습니다. 수열을 순서대로 살펴보면서 $a_{i} = 1$인 항이 나온다면 지금까지 카운트 했던 항의 갯수만큼 순서쌍의 갯수가 늘어나므로 이를 누적시키고 새 항을 카운트합니다.

그런데 살펴보다가 $a_{i} \geq 3$인 항이 나올 수 있습니다. 해당 항을 기준으로 이전에 나오는 값이 1인 항과 이후에 나오는 값이 1인 항을 사용하면 $\max(\{a_{i}\}_{i=l}^r) \leq 2 \cdot a_{l-1}$에 위배되므로 이전에 카운드 했던 항의 갯수는 사용할 수 없습니다. 즉, 해당 항 이후부터 다시 카운트합니다. 참고로 다음항으로 넘어갈 때마다 +1 또는 -1이 되므로 $a_{i} = 3$인 항을 만날 때만 다시 세면 됩니다. 어차피 $a_{i} > 3$인 항을 만나기 위해서는 값이 3인 항을 거쳐야하기 때문입니다.

그렇다고 $a_{r} = a_{l-1}$이 가질 수 있는 모든 값에 대해 위 방법대로 따로 구하면 시간이 오래걸립니다. 하지만 아래와 같이 구하면 모든 케이스를 동시에 고려하면서 계산할 수 있습니다.

1. $ans = 0$, $cnt[i] = 0$으로 초기화 합니다.
2. $a_{0}, a_{1}, \cdots , a_{|s|}$을 순서대로 살펴보면서 다음 과정을 수행합니다.
   $\quad$ 2-1. $ans$를 $cnt[a_{i}]$만큼 증가시킵니다.
   $\quad$ 2-2. $cnt[a_{i}]$를 $1$ 증가시킵니다.
   $\quad$ 2-3. $a_{i}$가 홀수라면 $cnt\left[\lfloor \frac{a_{i}}{2} \rfloor\right]$를 $0$으로 설정합니다.
3. $ans$를 출력합니다.

수열 $a$를 구하는데 $O(|s|)$, 순서쌍의 갯수를 구하는데 $O(|s|)$만큼의 시간이 걸리므로 시간복잡도는 $O\left( \displaystyle\sum{|s|} \right)$입니다.