二分ヒープを書きました 二分ヒープ is 何 平たく言えば std::priority_queue みたいなやつ 次の操作がいい感じの計算量でできる top() 最大値を取得する $O(1)$ pop() 最大値を削除する $O(\log N)$ push(value) 値を追加する $O(\log N)$ 構造 二分木を持…

問題リンク 解説 まず、$N'$ 頂点の木に対しての場合を考える。 次数が奇数になる頂点の集合を適当にとると、要素数を $x$ 個として、$x$ が奇数ならそのような部分グラフは $0$ 通り、偶数なら $1$ 通りとなる。 $N'=1$ のとき明らかに成り立ち、それ以外は…

問題リンク 面白かった。 解説 まず、愚直な DP を考えてみる。「$dp[i][j] =i$ 番目までで、$j$ で終わっているときの、ここまでの置き方の通り数」とすると、自明に解けるが、これでは当然通らない。 $A_i$ を座標圧縮して、同じ区間に含まれる数はまとめ…

問題リンク シンプルながら FFT への帰着がきれいで、良い問題だと思う。 解説 ビット文字列 $T$ を $S$ の部分文字列とするには、最小何ビット反転させればよいかを求める問題。 単なる文字列検索なら KMP 法を使ったりすればよいが、今回はビットの反転数…

問題リンク 数え上げ，苦手 解説 数をグループにして考える．$h$ に含まれる $i$ の数を $n_i$ としておく． $n_i$ 個の数があるグループの中に重複を少なくとも $k$ ペア作る方法の数は $\binom{n_i}{2k}(2k-1)!!$ 通りある． これを多項式の係数にして畳み…