第１６回日本情報オリンピック 予選 D - ぬいぐるみの整理 (Plush Toys)
M種のぬいぐるみをN個並べる。N個の中から一斉に幾つか取り出し、順番を変えて元に戻した時同一種類のぬいぐるみは全部隣り合う用に並べたい(11112222223333 のように) 取り出す数の最小値を求めよ。
Mが20程度なのでBitDPを疑う。M種の中からK種を選び、そのK種が左から順番に並んでいる状況を考えると、これはK-1種(これはK通り)を順番に並べた時からもう一種追加した、という遷移に等しい。このようなdpで取り出すぬいぐるみの数の最小値を計算する。
左のlからrにかけてある1種のぬいぐるみを並べるときに取り上げなくてはならないぬいぐるみの数は累積和などをあらかじめ計算しておくことでO(1)で計算可能。よってdpの遷移はO(M)で行える。総計算量はO(2^M * M)。
ちなみにdpでやる方法は難しい(ビットがk個立ってるという順列を作る方法が難しい)のでメモ化再帰でもいいかもしれない。
追記
こういうbit DPを組むときは一つ前を考えるのではなく、一つあとを考えると良いらしい。つまりdp[s] = ～～～ではなく、dp[s | (1 <<i)] = Math.min(dp[s | 1(<<i)], dp[s] + x)のように遷移させると、0～1<<M までの遷移が順番に並ぶ。これは覚えておきたい。
