TopCoder SRM 695 (Div. 1) Easy. BearPasswordLexic

問題

一種類の文字のみで構成された文字列を constant string と呼ぶ。

ある文字列 S の部分文字列のうち、長さ i でかつ constant string であるものの個数を x[i] とする。x が与えられるので S として考えられる辞書順最小のものを答えよ。もしないなら空文字列を返せ。

• 1≦n≦50

解法

aaaabbbbaabという文字列は、連続する文字長を要素とする数列 [4,4,2,1] で表せる。

数列を単調減少に限定すると、このような数列の個数は分割数 p(n) になる。

p(50)=204226 なので、単調減少に限定すれば全通り列挙する時間の余裕があるということになる。

この問題では辞書順最小の解を要求しているので、列挙した単調減少な数列を a[n] としたとき、a[0]→a[-1]→a[1]→a[-2]→a[2]→…のように並び替えたものを解にする。ここで、a[-i] は後ろから i 個目の要素を表す。

本番では辞書順最小を見落として systest failed。本文中に書いてあるし、サンプルにも書いてあるし、問題名にも lexic って入ってるし、何故気づかなかったんだろう。