ARC175 python Atcoderの記録

問題はこちら
1完

A
くそ汚いコード。後で書き直したい。

N = int(input())
P = ["-"] + list(map(int, input().split()))
S = "-" + input()
"""
結局みんな右で取るor左で取るを合わせる必要がある。
dp[i]: P[i-1]の人までスプーンをとった時の聞き手の組み合わせ＝Sの有り得方
dpの遷移(右側をとることが確定しているとき) 
dp[i] = dp[i-1] *2 if S[P[i]]が両方を選べるとき→スプーンが右側にしかなく、？の時→S[P[i]]が？で、i+1のスプーンしかないとき
dp[i] = dp[i-1]  if P[i]がどちらかを選べるとき→S[P[i]]がLかRで、i+1のスプーンしかない。または→S[P[i]]がRで、両方のスプーンがある。
dp[i] = 0 P[i]が右のスプーンを選べないとき→S[P[i]]がLで、両方のスプーンがあるときor スプーンがない
"""
MOD = 998244353
# 右のスプーンをとるときのdp
dp_R = [1]
spoon = [[] for _ in range(N+1)]
for i in range(N+1):
    spoon[i] = ["L", "R"] if i != 0 else []

for i in range(1,N+1):
    if (S[P[i]] == "L" and spoon[P[i]] == ["L", "R"]) or (spoon[P[i]] ==["L"]) or (spoon[P[i]] ==[]):
        dp_R.append(0)
        break
    elif S[P[i]] == "?" and spoon[P[i]] == ["R"]:
        dp_R.append(dp_R[-1] *2 % MOD)
        spoon[P[i]] = []
        index = P[i] + 1
        if index == N+1:
            result = spoon[1].remove("L")
        else:
            result = spoon[index].remove("L")

    else:
        if spoon[P[i]] == ["L", "R"]:
            dp_R.append(dp_R[-1])
            spoon[P[i]] = ["L"]
            index = P[i] + 1
            if index == N+1:
                result = spoon[1].remove("L")
            else:
                result = spoon[index].remove("L")

        elif spoon[P[i]] == ["R"]:
            dp_R.append(dp_R[-1])
            spoon[P[i]] = []
            index = P[i] + 1
            if index == N+1:
                result = spoon[1].remove("L")
            else:
                result = spoon[index].remove("L")
# 左のスプーンをとるときのdp
dp_L = [1]
spoon = [[] for _ in range(N+1)]
for i in range(N+1):
    spoon[i] = ["L", "R"] if i != 0 else []

for i in range(1,N+1):
    if (S[P[i]] == "R" and spoon[P[i]] == ["L", "R"]) or (spoon[P[i]] ==["R"]) or (spoon[P[i]] ==[]):
        dp_L.append(0)
        break
    elif S[P[i]] == "?" and spoon[P[i]] == ["L"]:
        dp_L.append(dp_L[-1] *2 % MOD)
        spoon[P[i]] = []
        index = P[i] - 1
        if index == 0:
            result = spoon[N].remove("R")
        else:
            result = spoon[index].remove("R")

    else:
        if spoon[P[i]] == ["L", "R"]:
            dp_L.append(dp_L[-1])
            spoon[P[i]] = ["R"]
            index = P[i] - 1
            if index == 0:
                result = spoon[N].remove("R")
            else:
                result = spoon[index].remove("R")
        elif spoon[P[i]] == ["L"]:
            dp_L.append(dp_L[-1])
            spoon[P[i]] = []
            index = P[i] - 1
            if index == 0:
                result = spoon[N].remove("R")
            else:
                result = spoon[index].remove("R")

print((dp_R[-1] + dp_L[-1])%MOD)

B
解説AC
交換したときに累積和が最大で2増加することに気づかなかった。

N, A, B = list(map(int, input().split()))
S = input()
# (なら+1、)なら-1として累積和と途中の最小値を計算。累積和//2が置換の必要数
# またリストのほうが後で都合がよいのでリストに格納
list_S = []
min_count =  float('inf')
fin_count = 0
for s in S:
    if s == "(":
        fin_count += 1
    if s == ")":
        fin_count -= 1
    min_count = min(min_count, fin_count)
    list_S.append(s)
# print(min_count, fin_count)

# 置換のコストを求める
cost = (abs(fin_count)//2)*B
# 置換後のSを考える
if fin_count > 0:
    swap_count = 0
    for i in range(len(list_S)-1,-1,-1):
        if list_S[i] == "(":
            list_S[i] = ")"
            swap_count += 1
            if swap_count >= abs(fin_count)//2:
                break
if fin_count < 0:
    swap_count = 0
    for i in range(len(list_S)):
        if list_S[i] == ")":
            list_S[i] = "("
            swap_count += 1
            if swap_count >= abs(fin_count)//2:
                break
# print(cost)
# もう一度累積和をとって交換の必要回数を求める
min_count = 0
fin_count = 0
for s in list_S:
    if s == "(":
        fin_count += 1
    if s == ")":
        fin_count -= 1
    min_count = min(min_count, fin_count)
# 交換のコストを求める。1交換すると最大で累積和が+2されることに注意
if min_count < 0:
    cost += (abs(min_count)+1)//2 * min(A, 2*B)
print(cost)