SRM405 Div2 1000

問題

ideal文字列とは，(1-basedなインデックスで)各アルファベットが最初に現れる位置のインデックスの個数出てくるような文字列をいう．ある整数lengthが与えられるので，辞書順で最小となるideal文字列を返す．もしあり得ないときは空文字を返す．

考え方

A,B,C,...と順番に入れる場所を考える．
順番に入れるので，そのアルファベットが最初に現れるインデックスをそれぞれ保持すると，
1+2+3+...
1+2+4+...
のような足し算と見なすことができる．
i番目の数字は，(i-1番目の数字+1)から，(i-1番目までの数字の和+1)までを取ることができることがわかるので，和がlengthとなる最初の足し算の組み合わせをdfsで見つける．
ただし，文字列に直した時に，同じ文字数でも辞書順で小さくなるようにしなければならないので，dfsでi番目の数字を決める時は，(i-1番目までの数字の和+1)から(i-1番目の数字+1)へ逆に探していく．．