読者です 読者をやめる 読者になる 読者になる

ゆらのふなびと

競プロ, Python, C++

AOJ-ICPC 400 お姫様の暗号解読

問題

Princess, a Cryptanalyst | Aizu Online Judge

N個の文字列が与えられる。これらすべてを部分文字列として含む最小長さの文字列を求めよ。ただし、最小長さの文字列が複数ある場合はそのうち辞書順最小のものを答えよ。

制約

1 <= N <= 10

各文字列 s_i の長さは10文字以下

文字列はアルファベット小文字からなる

解法

http://acm-icpc.aitea.net/index.php?plugin=attach&refer=2008%2FPractice%2F%E6%A8%A1%E6%93%AC%E5%9B%BD%E5%86%85%E4%BA%88%E9%81%B8%2F%E8%AC%9B%E8%A9%95&openfile=E.pdf

解説を見たら実は全探索でも間に合うらしいんですが、DPで解いたのでDP解法を紹介します。

以下、文字列長の最大値をLとおきます。

DPで解くことを考えたとき、困るのは連結するときのコストの計算です。S = w_1 w_2 ... w_m (w_iは単語)という文字列ができているとき、この右側に w_{m+1} をつなぐことを考えましょう。w_{m+1} のprefixが S のsuffixと共有する部分が w_m の範囲に限られればいいのですが、もっと前の単語まで伸びると毎回コストを計算してあげなければならず詰みそうです。ところが、もしそのような(直前の単語より前まで共有されるような)場合には w_m は w_{m+1} に完全に含まれていることになります。そこで前処理として、他の単語に完全に含まれるような単語を消しておきましょう。するとSに新しい単語をつなぐときのコストが直前に採用した単語と次に採用する単語のみからわかることになります。

単語を頂点とし、有向辺を各頂点間に両向きに張ったグラフGを考えます。辺 i->j のコストは s_i の後ろに s_j をつないだときに共有できる文字数とします。するとこの問題は、G上の最長ハミルトンパスを求める問題に帰着されました。あとはよくあるbitDPです。辞書順最小のものを求めたいので、実際にはdp配列に文字列そのものをもってやるといいみたいです。

以下のコードは頭がないので文字列長でDPしたあと経路復元して最小のものを求めています。

gist.github.com