SRM428 Div2 500
問題
ある文字列が与えられる.その文字列の文字を入れ替えることができるとき,2回以上連続して同じ文字がならばないような文字列の個数はいくつ作れるかを返す.
考え方
その文字列で使われている文字の個数を文字ごとにカウントしていって,dfsで作れるかどうかを調べた.dfsは,前の使われた文字を引数にして,
- もしすべての文字を使いきっていたら作れたのでret++
- もし前に使った文字以外がすべてなくなってしまったら作れないのでそのまま終了
- それ以外なら,使える文字iのカウントを減らしてdfs(i)する
にした.
反省
文字数が10文字までなので,next_permutationでやっても10!=3628800しかない.なので,それで文字列を作って,連続した文字がないかどうかをチェックすれば速かった.