Entries

スポンサーサイト (この記事を編集する[管理者用])

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/1419-793f81bb
この記事にトラックバックする(FC2ブログユーザー)

Aizu 1170 - Old Memories (古い記憶) (この記事を編集する[管理者用])

Source

ACM/ICPC Japan 2010 Domestic
Aizu 1170

問題概要

この問題は文字列といえば,アルファベットとピリオドの27文字からなるとする.
40文字以下の文字列Aと,30個以下だけ13文字以上20文字以下の文字列B[i]が与えられる.
 どの文字についても,その文字を含む部分文字列の中で,Bの要素を一致するものが存在する
 d回以下の,文字の挿入,文字の置き換え,文字の削除の操作でAにできる (編集距離がd以下)
を満たすような文字列の数を求める問題.
もし,答えが5以下なら,ついでに列挙する.
dは2以下.

解法

Bを繋ぎあわせてできる,Aの文字数と高々d違う文字列を列挙して,編集距離がd以下かどうかDPで判定した.
途中までの編集距離から枝刈りも行った.
(ニコニコ生放送で書いた時のコードから,同じ文字列を生成してしまったときに,枝を刈る前に,新しい文字列で編集距離のDPを計算しているという無駄なことをやめたら2倍ぐらい速くなった)

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/1419-793f81bb
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。