「 今週のお題：圧縮できるパターンは何通り？」問題解答 ( CodeIQ )

CodeIQ

はじめに

CodeIQという所で週次で出題される「今週のお題」シリーズに解答しましたので、ネタバレです。

codeiq.jp

問題

今回は次のような問題でした。

  • カンマ区切り1行で入力される m,n ( $m^n\le 65536$ ) に対して、「高々m種類のアルファベットで構成されるn文字の文字列」の中で、ランレングス圧縮で文字数が縮むものが何通りあるかを出力する。
  • ランレングス圧縮は、同じ文字の塊を、「当該文字+塊の文字数」に置き換えるものとする。
    例えば、AABBBCEEEE→A2B3C1E4

解説

提出したのは、次のRuby(70)でした。

m,n=eval ?[+gets+?]
s=t=m
(n-3>>1).times{|i|s+=t=t*~-m*(n-=1)/-~i}
p s

当初は、次のように考えていました。

連続する同じ文字の塊で分割し、$k$個の領域に分かれる場合、その分け方がどうであれ、圧縮後の文字数は $2k$ になります。
かつ、$k$個の領域への分け方は ${}_{n-1}C_{k -1}$ ( $n-1$箇所の候補に、$k -1$個のくさびを打って$k$個に分けるから ) と、$m(m -1)^{k -1}$ ( 最初だけ$m $種類、後は直前の文字を避けてそれぞれ$m -1$種類ずつ ) の積であるため、解は、 $\sum_{1\le k\lt \frac{n}{2}}^{}{}_{n-1}C_{k -1}m(m -1)^{k -1}$と計算できます。

ただ、良く考えると、強調部分の「圧縮後の文字数は $2k$」は嘘ぴょんなのですね。なぜならば、塊が10文字以上の場合を考慮していないため。例えば、“AAAAAAAAAA”というA10文字の場合、$k=1$に該当しますが、圧縮後は“A10”の3文字です ( そうなることは、問題文に明示はされていませんが… )。ですが、全ケースパスしています。…どうしてでしょう??

正しい解と差が出るとすれば、以下に該当する場合です。

  • $1\le k\lt \frac{n}{2}$であるけれども
  • 文字の塊の一部が10文字以上となることで
  • 圧縮後の文字数が $2k$ より大きくなり、結果 $n$ 以上となる

が、$m^n\le 65536$ のため、実は今回の問題では考慮する必要がないのでした ( 最悪のケースでも $m=2, n=16$ であり、10文字×1+1文字×6→圧縮後15文字でセーフ )。うまい具合にできてますね。

終わりに

これ、でも、数字が複数桁になるのをケアしようとすると、結構大変なことになりそうですね。