Hatena::Grouptopcoder

TopCoder煮ブログ

本家ブログはこっち → http://d.hatena.ne.jp/nitoyon/

2008-11-02

ClosestRegex (SRM410 DIV2 Hard)

| 00:29 | ClosestRegex (SRM410 DIV2 Hard) - TopCoder煮ブログ を含むブックマーク はてなブックマーク - ClosestRegex (SRM410 DIV2 Hard) - TopCoder煮ブログ

text に最も近い正規表現にマッチするものを求める問題。正規表現は50文字までなのだけど、"a*b*c*d*..."のようなパターンだと正攻法で解いたら計算時間がひどいことになる。それを解決するためには、おそらく DP でなんとかするんだろうが、やっぱりひらめかない。DP 弱い。Match EditorialsDynamic Programming: From novice to advancedというリンクが。おお、こんな素敵なチュートリアルがあったのか! 他にも左メニューの「Algorithm Tutorials」には魅力的な文章がいくつも。このあたりをまずは一読しておくとよさそうだ。

一読して、そのあとにしばらく考えたらひらめいた。DP[i]には文字数が i の正規表現のうち、text にマッチする数が最小となるものを保存すればよい。atomでforを回して、DP[i] を更新していく。atom が * の場合には DP[i] を右短まで更新して、* がない場合には1つ進める。例えば、1) の例だと、最初の t* を解釈したときの DP は次のようになる。

DP[0]: 0  // ""
DP[1]: 0  // "t"
DP[2]: 1  // "tt"
DP[3]: 2  // "ttt"
DP[4]: 3  // "tttt"
DP[5]: 4  // "ttttt"
DP[6]: 5  // "tttttt"
DP[7]: 6  // "ttttttt"
DP[8]: 7  // "tttttttt"

次の p を解釈したらこうなる。

DP[0]  ∞ // ""
DP[1]  1  // "p"
DP[2]  1  // "tp"
DP[3]  1  // "ttp"
DP[4]  3  // "tttp"
DP[5]  4  // "ttttp"
DP[6]  5  // "tttttp"
DP[7]  6  // "ttttttp"
DP[8]  7  // "tttttttp"

DP[0] はありえないので∞にしている。こんな感じで続けていけばおk