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.
-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.
--YES as long as the number of characters is even, 1. ")" is not the first character, and 2. "(" is not the last character.
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.
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.
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
Recommended Posts