第二回 PAST K - 括弧

問題原文

atcoder.jp

問題要旨

(, ) からなる を対応の取れた括弧列にすることを考える。
まず、以下の操作を0回以上行う。

• 文字目の ( と ) を反転させる。コストとして かかる。

次に、以下の操作を0回以上行う。

• 文字目を削除する。コストとして かかる。

を対応の取れた括弧列にするための最小コストを求めよ。

• 

解法

atcoder.jp

↑をやっておくと、 ((の個数) - ()の個数) での状態の同一視が思い浮かぶ。
あとは、

文字目までみて ((の個数) - ()の個数) が のような状態にするための最小コスト

として、丁寧にdpテーブルを埋めていけば終わり。
各文字について、操作１と２の両方をやることは明らかに損なので、同時に好きな操作を選べると考えて大丈夫。

魔力発電をやってなくても「対応の取れた括弧列かどうか」の判定ロジックを考えると、

1. それまでの ( の個数が ) の個数以上。
2. 最終的な ( の個数と ) の個数が同じ。

にたどり着けて、そこからテーブル定義が見えそう、な気がする。

atcoder.jp

をやっておくと、ここまではわかるかも。

実装

丁寧に。

N = int(input())
S = input()
C = list(map(int, input().split()))
D = list(map(int, input().split()))
 
# dp[i][j]:= i文字目まで見たときに「(の数 」- 「)の数」をjにするための最小コスト
dp = [[float('inf')] * (N + 1) for _ in range(N + 1)]
dp[0][0] = 0
for i, s in enumerate(S):
    if s == '(':
        for j in range(N + 1):
            cost0 = dp[i + 1][j]
            cost1 = float('inf')  # そのまま
            cost2 = float('inf')  # 変換
            cost3 = float('inf')  # 削除
 
            if j - 1 >= 0:
                cost1 = dp[i][j - 1]
 
            if j + 1 < N:
                cost2 = dp[i][j + 1] + C[i]
 
            cost3 = dp[i][j] + D[i]
 
            dp[i + 1][j] = min(cost0, cost1, cost2, cost3)
 
    elif s == ')':
        for j in range(N + 1):
            cost0 = dp[i + 1][j]
            cost1 = float('inf')  # そのまま
            cost2 = float('inf')  # 変換
            cost3 = float('inf')  # 削除
 
            if j + 1 < N:
                cost1 = dp[i][j + 1]
 
            if j - 1 >= 0:
                cost2 = dp[i][j - 1] + C[i]
 
            cost3 = dp[i][j] + D[i]
 
            dp[i + 1][j] = min(cost0, cost1, cost2, cost3)
 
 
print(dp[-1][0])

感想

これ瞬殺できたのは確実にJOI精進のおかげだなぁと思います。
でも今だと緑diffつきそうでこわいね。