問題
N個の文字が与えられる。これらの文字を使って以下の性質を満たす文字列の数を求めよ。
- 同じ文字が連続しない
- xyxyの形式を持たない。x=yの場合も含み連続している必要はない。
- 1,2の性質を満たす文字列の中で最長
解法
まず、文字列の長さの最大を求める。
最長の文字列は2N-1となる。簡単な証明を以下に示す。
2の性質より、同じ文字で囲まれた文字は使用できなくなる。abcaという文字列を考える。aに囲まれているb,cを文字列の後ろに追加すると2の性質を満たせなくなる。つまり、すでに含まれている文字を追加すると必ず1つ以上の文字が使えなくなる。同じ文字は連続できないので、間にはなんらかの文字列が必ず存在する。文字列を最長にするためには、文字の減少量を最小にすれば良い。つまり、1にすれば良い。よって、2N-1が最長になる。
最長の文字列の形式は以下の2つになる。
- aX...Xa
- aX...XaY...Ya
2の性質により、同じ文字は4回以上使用することはできない。
X..X、Y..Yは性質を満たす文字列である。ひとつの形式に対してはN!の文字列が存在する。文字数Nの時の形式の数Sは以下の式で表される。
これを動的計画法で求めれば、答えが求まる。
計算量