TopCoder SRM 686 (Div. 2) Hard. BracketSequenceDiv2

最初 Div 1 と同じ問題だと思ってスルーしそうになった。

問題概要

() で構成された文字列が与えられる。いくつかの文字を削除して作ることのできる正しい括弧列は何通りあるか。

Div 1 は文字の消去パターン数を求める問題だったのに対し、こちらは出来上がる文字列の種類数を求める問題であることに注意。

解法

以下の問題を解いたことがあれば似たような手法が取れる。

しかし、これらの問題は数え上げパート以外が面倒なので類題として勧めにくい。


最後に使った文字がオレンジの場所のとき、次に使う文字を赤色のものだけに限定することで二重カウントを回避できる。 赤色の文字はオレンジより後ろにある最も近い () である。

f:id:pekempey:20160329173152p:plain

赤の文字を使わずにオレンジで括弧列を終わらせるという遷移パターンもある。

用意するのは次のような DP テーブル。

  • dp[ 最後に使った文字の位置 ][ いくつの括弧が開いているか ] := この状態に至るパターン数

TopCoder SRM 686 (Div. 2) Hard. BracketSequenceDiv ...

類題を解いたことがあればすぐに解けるかもしれないが、解いたことがないなら結構難しいと思う。