TopCoder SRM689_Div2 : ColorfulGardenHard
TopCoder Statistics - Problem Statement
問題
花の種類を表す文字列 と ある位置における配置禁止の色 の二つの情報が与えられる。
花は色を持ちアルファベットで表現される。
与えられた花を以下の条件に従い並び替えた時、 そのパターンの総数を求めよ。 (重複は除く)
・ 同じ色の花が隣合わない
・ 位置iで禁止されている色を置いてはいけない
解放
文字列の長さが高々15のため、bitDPを利用できる。(制約からすぐに気付きたい)
重複を避けるために各bitマスクの状態で、次に追加する特定の色が2回以上選択されないように注意する。
計算量は となる。
・ bitマスクの状態数 通り
・ 最後に選択した色 通り
・ 各状態に対して、最大 通りの次に選ぶ花の選択技
