Deciphering(解読) - joi2011-day3 解説

筆者: qnighy

原文が暗号文の部分列であり、原文中で隣接してよい文字の組が与えられたとき、原文として考えられる列を数え上げる問題である。(このとき、原文中の文字がもともと暗号文のどの位置であったかは区別しない。)

10点解法

全ての組み合わせを数え上げれば10点が期待できる。

…

例えば、「ABCDBCD」という列を考え、Dで終わる列に注目してみよう。

すると、次のことがわかる: 「A.CD…」のように、1番目のDで終わるような列は、必ず「A….CD」や「A.C…D」のように、2番目のDで終わるような列としても出現する。

これを利用して漸化式を立てる。

今回のDPは、暗号文を手前から順番に走査していく一般的なDPである。

各状態において、

dp(i, X) = (i番目の文字まで処理したところで、文字Xを末尾に据えて作ることのできる部分列の個数)

を置く。

i番目の文字がXでないときは、dp(i, X)はdp(i-1, X)と等しい。
文字Xそれ自身も有効な列なので、1を足す必要がある。
現在処理しているXよりも前のXの出現時点で数えたことのあるものを再度数えてはいけない。幸い、今まで数えたそれらの場合の数、すなわちdp(i-1, X)を引けばよいだけである。

上記の結果をまとめると、以下のような漸化式になる。