bitDP に関するカテゴリーです。

AtCoder, bitDP, 動的計画法

問題方針考察

鍵 \( i \) は \( b_i\) 種類の宝箱を開けることができるので、鍵は鍵束であると見ることができます。全ての宝箱を開けられないときは、全ての鍵の集合に対して対応できない宝箱があるということなので、先にそれのチェ ...

AOJ, bitDP, 動的計画法, 累積和

問題方針

素直に浮かぶ方針は、並び方を全通り試すという方法ですが、このときの場合の数は、\( M!\) となるので、計算量が多すぎます。ここで、次のことに着目します。ぬいぐるみを \( k \) 種類整列済みであるとき、\( k + 1 ...

bitDP, yukicoder, 動的計画法

問題方針

\( k \) 個商品を購入したとき、\( k + 1 \) 個目の商品を購入するときの割引は、\( k \) 個商品を購入したときの順番に依存しません。この考えをもとにして、bitDP を行います。

bitDP

\ ...