誤読するとAにしては重い問題だったのですが、重い方の解き方をメモ。
概要
- "("と")"と"?"でなる文字列があります。"?"はそれぞれ"("か")"に変換します。
- 変換は必ず実施しなければならず、括弧や?の入れ替えや削除はNGです。
- "("および")"は文字列に1回のみ出現します (これを読み飛ばしている人が多かった)
- 文字数は100以内です。
()の対応が正しいかをYES/NOで回答してください
正しく文章を読んでいた場合の想定解法
- 文字数が偶数であり、1.")"が1文字目ではない かつ2."("が最後の文字でない かぎりYESです。
括弧の対応の確認の仕方
競技プログラミングで括弧の対応を確認するのは典型です。
- "("を$+1$, ")"を$-1$として扱う.最後に0であればOK。この計算を「カウント」と以降呼びます。
- 途中で負の数になってはいけない。例えば"())("などは合計で0だが、3文字目で-1になる
DPでの解き方
上記の状態をDPで解きます。$i$文字目のカウンタ$j$である状態数を$dp[i+1][j]$で示します。初期状態は$dp[0][0] = 1です。(1文字も選択されていないときのカウンタの状態は1通りしかありません)
i文字目をすべて以下のように処理していきます。$k$は各カウンタの値です。
- i文字目が"("のとき、$dp[i+1][k+1] += dp[i][k]$です
- i文字目が")"のとき、$dp[i+1][k-1] += dp[i][k]$です。ただし、$k=0$の時、この計算は行いません。$k=-1$はカウンタが0未満になる状態なので、失敗する状態だからです。
- i文字目が"?"のとき、$dp[i+1][k+1] += dp[i][k]$ および $dp[i+1][k-1] += dp[i][k]$です。(同様に$k=-1$になる状態は処理しません)
この結果、$dp[n][0]$が0でなければ、つまり、最後の文字に到達したときにカウンタが0以外であれば、条件を満たせる遷移が存在するためYESを出力します。
実装
do_dp()がdp解法です。do()が想定解法(多分)です。
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()