[PYTHON] Codeforces Educational Codeforces Round 101 A. Regular Bracket Sequence Check the parentheses and? String in DP

https://codeforces.com/contest/1469/problem/A

If you misread it, it was a heavy problem for A, but make a note of how to solve the heavier one.

Overview

-There is a string consisting of "(" and ")" and "?". Each "?" Is converted to "(" or ")". --Conversion must be performed, and replacement or deletion of parentheses and? Is NG. - "(" and ")" appears only once in the string (many people skipped this) --The number of characters is 100 or less.

Please answer YES/NO whether the correspondence in () is correct.

Assumed solution when reading the text correctly

--YES as long as the number of characters is even, 1. ")" is not the first character, and 2. "(" is not the last character.

How to check the correspondence of parentheses

It is typical to check the correspondence of parentheses in competitive programming.

-Treat "(" as $ + 1 $, ")" as $ -1 $. Finally, 0 is OK. This calculation is hereafter referred to as "counting". ――It should not be a negative number on the way. For example, "()) (" is 0 in total, but it becomes -1 in the third character.

How to solve with DP

Solve the above state with DP. The number of states that is the counter $ j $ of the $ i $ character is indicated by $ dp [i + 1] [j] $. The initial state is $ dp [0] [0] = 1. (There is only one counter state when no character is selected)

Process all i-th characters as follows. $ k $ is the value of each counter.

--When the i-th character is "(", it is $ dp [i + 1] [k + 1] + = dp [i] [k] $ --When the i-th character is ")", it is $ dp [i + 1] [k-1] + = dp [i] [k] $. However, this calculation is not performed when $ k = 0 $. This is because $ k = -1 $ is a state in which the counter is less than 0, so it fails. --When the i-th character is "?", $ Dp [i + 1] [k + 1] + = dp [i] [k] $ and $ dp [i + 1] [k-1] + = dp [ i] [k] $. (Similarly, the state where $ k = -1 $ is not processed)

As a result, if $ dp [n] [0] $ is not 0, that is, if the counter is non-zero when the last character is reached, YES is output because there is a transition that can satisfy the condition.

Implementation

do_dp () is the dp solution. do () is the assumed solution (probably).

def do():
    s = input()
    if len(s) % 2 == 1:
        print("NO")
        return
    l = s.find("(")
    r = s.find(")")
    if r == 0 or l == len(s)-1:
        print("NO")
        return
    print("YES")
def do_dp():
    s = input()
    n = len(s)
    dp = [[0] * (100 + 10) for _ in range(100 + 10)]
    dp[0][0] = 1
    for i in range(n):
        ch = s[i]
        if ch == "(":
            for k in range(105):
                dp[i+1][k+1] += dp[i][k]
        elif ch == ")":
            for k in range(105):
                if k != 0:
                    dp[i + 1][k - 1] += dp[i][k]
        else:
            for k in range(105):
                dp[i+1][k+1] += dp[i][k]
                if k != 0:
                    dp[i + 1][k - 1] += dp[i][k]
    print("YES" if dp[n][0] != 0 else "NO")

q = int(input())
for _ in range(q):
    do_dp()

https://codeforces.com/contest/1469/submission/102673917