コンテストでの時間切れや解けなかった過去問を振り返って供養していく
問題
Difficulty: 1814 (記事作成時点)
供養
解法
- $(1, \dots, N)$ の部分集合 $S$ について、以下の条件を満たす数列の数を $\mathit{DP}_{S}$ とするbitDPをする
- 数列が $S$ で構成されている
- $1 \le i \le M $ について、$X_{i} \le |S|$ である条件をすべて満たしている
- $\mathit{DP}_{S}$ は以下のように計算できる
\begin{align}
\mathit{DP}_{S} =
\begin{cases}
1 & \; S = \emptyset \\
\sum_{x \in S} \mathit{DP}_{S \setminus \lbrace x \rbrace} & \; \mathrm{if} \; X_{i} \le |S| \; \text{の条件をすべて満たしている} \\
0 & \; \mathrm{else}
\end{cases}
\end{align}
- $X_{i} \le |S|$ の条件をすべて満たしているかは、$X_{i} = |S|$ の条件についてのみ考えればよい
- $X_{i} \lt |S|$ であるような条件は $S \setminus \lbrace x \rbrace$ の構築以前に確認済
- $\mathit{DP}_{(1, \dots, N)}$ が答え
- $S$ に対応する数 $A$ について、$P_{A} = |S|$ であるような $P$ を前計算しておけば高速化が可能
- $(1, \dots, Y_{i})$ に対応する数 $B$ について、$P_{A \; \mathrm{AND} \; B} \le Z_{i}$ ならば $S$ はその条件を満たしていると言える
実装
計算量は $O((N + M)2^{N})$
公式解説
躓いた点
- 何を保持しながらbitDPをしたらよいかを思いつかなかった
