動的計画法の次のステップとしてビットDPというものがあります.
1. そもそもビットDPって何？
普通の動的計画法は
a. dpの設定
b. 初期値の設定
c. 更新方法の設定
d. 出力の設定
を行います.
(例: フィボナッチ数列(今更聞けない) by making111 アクセス日 2021/08/22)
ビットDP(bit DP)の考え方 ~集合に対する動的計画法~,
アルゴリズムロジック アクセス日 2021/08/21によると,
ビットDPも基本的な動作はdpと変わらないみたいです.
しかし,ビットDPの変わった点として dpの設定を
\begin{align}
𝑑𝑝[𝑆]:=&{\rm 集合} S {\rm に対しての}{何かしらの値}
\end{align}
と定義することにあります.
これの何がbitかというと集合が0-1bitで表現されていることにあります.
(ex. 0010 -> {1}, 1110->{3,2,1} など)
では,AtCoder Beginner Contest 215 E問題 アクセス日 2021/08/21に当てはめて,考えてみましょう(問題概要はページを参照してください).
2. 例題の解説
私でも理解できるように,
公式解説 accessed 2021/08/21を噛み砕いていこうと思います.
今回の答えは解説にある通り以下のようにbitDPを実装します(10種類を$K$種類として表す).
a. dpの定義
\begin{align}
dp[i][P_i][k]:=&i{\rm 回目までの大会のうち,参加したコンテスト集合が}P_i{\rm で}\\&{\rm 最後に参加したコンテストの種類が}k{\rm であるような場合の組み合わせの数}
\end{align}
b. 初期値の設定
\forall i\in [0,N], \forall U,\forall k\in [K], dp[i][U][k]=0
c. 更新方法の設定
\begin{align}
{\rm for} \ i &\in {[0,N-1]}:\\
&{\rm Step1. \ \ }\forall U,\forall k\in [K], dp[i+1][U][k]+=dp[i][U][k] \\
&{\rm Step2. \ \ } {\rm if} \ S_i=k: dp[i+1][U][k]+=dp[i][U][k] \\
&{\rm Step3. \ \ }\forall U{\rm (which\ doesn't\ include\ }S_i{\rm )},\forall k\in [K],\\
&\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ dp[i+1][U\cup \{S_i\}][S_i]+=dp[i][U][k]\\
&{\rm Step4. \ \ } dp[i+1][\{S_i\}][S_i]+=1
\end{align}
(意味は,
1. i+1回目の大会は参加しないパターンを追加
2. i+1回目の大会に参加しても,参加したコンテスト集合が変化しない場合
3. i+1回目の大会に参加できるが,参加したコンテスト集合が変化する場合
4. 今まで何も参加していない場合を,初期値の設定上,追加する必要がある)
d. 出力の設定
\sum_{U,k} dp[N][U][k]
以上のように設定すれば良いです(ほとんど解説の通りです).
このように例を見ると,いかに集合をbitとして扱うのが革新的かわかる.
また,計算量に関しては,
各$i$に対して,$O(K2^K)$であり,$O(NK2^K)\simeq 10^7$で
制限時間が2秒のため問題なく実行できます.
3. 実行コード参考を読むのに必要な知識
今回は,本コンテストにおいてE問題をPythonで最も早く解いた
shotoyoo様のコード(アクセス日 2021/08/22)を参考にさせていただきます.
このコードを読む知識を簡単にまとめておきます.
>>> 1<<0
1
>>> 1<<1
2
>>> ord('a')
97
>>> 1&5
1
>>> 1|10
11
>>> 4|2
6
>>> 4>>2
1
>>> 4>>1
2
>>> 6>>3
0
この辺りがわかればあとは実装できると思います！
4. 結論
bitで集合扱うことで計算量の短縮にも貢献できることがわかりました.
(過去にpythonのbit処理をまとめてあるのでそちらもよければ参照ください
Python 論理積と右シフト by making アクセス日 2021/08/22)
bitDPの類題を今後解いていきたいと思います.