KMCの例会講座で用いたスライドを一部編集したものです。 ビット演算を組み合わせたトリッキーな方法で様々な操作を高速に行う方法を紹介します。
![プログラミングコンテストでの動的計画法](https://cdn-ak-scissors.b.st-hatena.com/image/square/5ef057cc39ae1a12840a6b5051147dd05abcfe00/height=288;version=1;width=512/https%3A%2F%2Fcdn.slidesharecdn.com%2Fss_thumbnails%2Fdynamicprogramming-100328100739-phpapp02-thumbnail.jpg%3Fwidth%3D640%26height%3D640%26fit%3Dbounds)
ビットDPとは ビットDP(bit DP) とは、ビットで表現した集合を添え字に持つ動的計画法(DP)のことです。 基本的には、以下のような DPを考えます。 漸化式の更新式としては、 $$dp[ S \cup \{v\} ] = dp[ S ] + cost(S, v)$$ のように集合を1つずつ増やしていく形になることが多いです。 この集合に対するDPによって、\(n\) 個のものに対して\(n!\) 通りの順序の中から最適なものを計算するのを高速化できる場合があります。 集合をビットで表現する 実際には集合を配列の引数にするために、集合を2進数で表現します。全体集合 {0,1,2,…,n-1} の部分集合 S を n 桁の2進数で表現するのです。 例えば、全体集合 {0,1,2,…,9} の部分集合 {0,3,5} については、0bit目と3bit目と5bit目が 1で、それ以外が0
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く