D リアルタイム

部分点しか取れなかった。 DFSでパターンを生成していき、与えられた条件を満たさない場合は再起を呼び出さないようにした。

解説動画を見て

ビットDPで組み合わせの数をインクリメントしていく。 DPの値は部分集合ないで与えられた条件を満たす組み合わせ数。

組み合わせの数は f(n) = n * f(n - 1) というようになっていて、１つ数を選んで、それ以外の部分の組み合わせ数 * n(n回数を選ぶ)となるので、組み合わせの数をインクリメントしていくことで、順々に組み合わせ数を導き出すことができる。

上記の1つ数を選んだ際に選んだ数を末尾に置くと考え、選んだ数とそれ以外の組み合わせが与えられた条件にそぐわない場合はスルーすることで、条件を処理することができる。

ライブコーディングを見る前にちゃんと理解できているかの確認のため、実装してみた。

ビット演算はまだ慣れないので、ちょっと引っかかるところはあったけど、わりとすんなり実装できた。

vector valid で、valid[mask]が有効かどうかを保持するのはわかりやすい。自分の実装では、条件の設定をvectorに保持して、bool is_valid(mask, pos) のようにしていたので、1つのvectorのみ表現することによって、だいぶスッキリする。

bool contain(mask, pos) でmaskにその数字が含まれているのかを判定する関数を作っておくと、ビット演算周りが整理しやすくなりそう。ビット演算の条件判定はぱっと見でわかりにくくて混乱の元になるので、関数にしてわかるやすい名前をつけてあげると良さそう。