きままにものづくり

日々の気付いたことなんかを書いてます。

SRM618Div1Medium

問題

N個の文字が与えられる。これらの文字を使って以下の性質を満たす文字列の数を求めよ。

  1. 同じ文字が連続しない
  2. xyxyの形式を持たない。x=yの場合も含み連続している必要はない。
  3. 1,2の性質を満たす文字列の中で最長

解法

まず、文字列の長さの最大を求める。
最長の文字列は2N-1となる。簡単な証明を以下に示す。
2の性質より、同じ文字で囲まれた文字は使用できなくなる。abcaという文字列を考える。aに囲まれているb,cを文字列の後ろに追加すると2の性質を満たせなくなる。つまり、すでに含まれている文字を追加すると必ず1つ以上の文字が使えなくなる。同じ文字は連続できないので、間にはなんらかの文字列が必ず存在する。文字列を最長にするためには、文字の減少量を最小にすれば良い。つまり、1にすれば良い。よって、2N-1が最長になる。

最長の文字列の形式は以下の2つになる。

  1. aX...Xa
  2. aX...XaY...Ya

2の性質により、同じ文字は4回以上使用することはできない。
X..X、Y..Yは性質を満たす文字列である。ひとつの形式に対してはN!の文字列が存在する。文字数Nの時の形式の数Sは以下の式で表される。
 S[N] = S[N-1] + \displaystyle{\sum^{N-2}_{p=1}(S[p]*S[N-1-p])}
これを動的計画法で求めれば、答えが求まる。

計算量

O(N^2)

コード