TopCoder SRM 688 (Div. 2) Hard. ParenthesesDiv2Hard

問題概要

括弧列 S といくつかの区間[Li, Ri]が与えられる。swap をすることにより全ての区間 [Li, Ri] に対し S[Li, Ri] が対応の取れた括弧列になるようにしたい。swap 回数の最小値を求めよ。もし不可能なら -1 を出力せよ。

なお、どの区間も重なっていないことが保証されている。

  • 1≦|S|≦50

解法

以下の DP を行う。

  • dp[ いま見ている位置 ][ 閉じていない括弧の数 ][ スタックに積んである '(' の数 ][ スタックに積んである ')' の数] := swap回数の最小値

遷移するときに考えるのは、

  • 区間外では「閉じていない括弧の数」を変更しない
  • 区間の最後では必ず「閉じていない括弧の数」は 0 でなければならない

ということ。

'(' と ')' をスワップする場合は、'(' をどこか別の所においておいて、どこかから ')' を持ってくると考えればいい。 置いておく場所を便宜上スタックと呼ぶことにした。

スタックに積まれた括弧の数は前借りできるように負の個数も許す。


よくよく考えると、'('の数+')'の数=0 なので 4 つ目の状態が不要になり O(n3)。O(n4) でも通るので放置した。

TopCoder SRM 688 (Div. 2) Hard. ParenthesesDiv2Har ...

提出を見る限り想定解は DP じゃないらしい。