CodeIQ 挑戦の記録 : 今週のアルゴリズム : 第96回「圧縮できるパターンは何通り」

CodeIQというサイトで問題に挑戦した記録です。

f:id:ibeckuu:20160523223811j:plain

問題文を要約すると下記の通り

方針

最大のケース（組み合わせ総数）が65536 (= ${{2}^{16}}$ )なので全探索でも解けると思ったが、組み合わせ論的に計算し、高速化を図ろうとした。が、結果的に失敗だった。
失敗というのは次の点から、

計算順序としては次の通り、

部分文字列のパターンの列挙
1からnまでの重複組み合わせで文字数がnのものの全てのパターンを再帰関数にて列挙する。
この時、短縮できる条件として、
1文字が連続する(2文字以上連続しない)部分文字列の個数をp、2文字が連続する部分文字列の個数をqとすると、元の文字列よりも短縮できる時、次の式がなりたつ。(式は短縮できる為の必要条件)

${{0} \leq {p}}$ < ${\lfloor {(n - 2q -1)} \div {2} \rfloor }$ 　（ ${ \lfloor }$ ${ \rfloor}$ は床関数）
これを同時に、式が成り立つならば短縮できると思い込み、必要十分条件と勘違いした事が、エラーの原因だった。
(短縮できない例)
n=8で、1文字の連続が2個、3文字の連続が2個のケースなど。
同じものを含む順列
連続する文字の個数の順列を同じものの個数の順列で割れば良い。
組み合わせ
連続する文字それぞれに対し、最初の文字はm種類でm通り、2種類目以降の文字はその前の文字を除く(m-1)通りが選べる。
これより、n文字の文字列中で、連続する部分文字列がk個あったとすると、
${m} \times {(m-1)}^{(k-1)}$ 通りとなる。

では、