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

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

CodeIQ

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

f:id:ibeckuu:20160523223811j:plain

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

  • ランレングス圧縮(連長圧縮)を考える
  • 例えば、「AABBBCEEEE」の場合は「A2B3C1E4」のように変換する。この場合元の文字列が10文字に対し変換後8文字に短縮できる。
  • 標準入力から整数m,nが与えられる。m種類のアルファベットでn文字の文字列の内、元の文字列より短くなるものの総数を解答する。
  • {{m}^{n} \leq 65536}

方針

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

  • 短縮できる条件の設定を間違い正解できないケースがあった。この原因が判明するのにコードを書いた以上の時間を要した。
  • 思ったほど高速化にならなかった。(最大のケースで約0.3秒)
  • ソースコードが長く可読性の悪いものになった。

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

  • n文字の文字列の中で、1文字からn文字までの同じ文字が連続する部分文字列が何個あるかのパターンを列挙する。
  • それぞれのパターンについて同じものを含む順列を計算する。
  • さらに、連続する部分文字列に対し、組み合わせを計算し、順列と掛け合わせたものの総和を解答とする。

計算の詳細

  • 部分文字列のパターンの列挙
    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)}通りとなる。

実装(Ruby)

では、



Sponsored Link