〈説明用メモ〉O(3^N)について本気出して考えてみた
個ある何かの0個以上から成る集合をビットの整数で表すことにする。
このとき、集合に含まれる要素が個なら全部でビット立っている 。
(__builtin_popcount(S) == k
)
この集合の部分集合をすべて列挙しようとすると、空集合も含め通りある。
集合Sとしてありうる全てのパターンについてこれを列挙することを考えると、
個から個選ぶ組み合わせが通りで、そのそれぞれについて通りの部分集合があるので全部で 通りについて考えることになる。
ここで驚くべきことは、任意の非負整数について
$$ \sum_{k=0}^{n}{_nC_k\cdot2^k}=3^n $$
が成り立つということである。
各ビットについて
- でもでも立っている
- でのみ立っている
- でもでも立っていない
の3通りの状態がありうるのだから自明ではある。
bitDP回りでよくという数が出てくるのはそのためである。
実際の回し方については
ビットによる部分集合の列挙 - SRM diary(Sigmar) - TopCoder部
の解説がわかりやすい。
意地悪な制約の問題では計算量 では間に合わず、 に下げる工夫が求められたりする。
高速ゼータ変換/高速メビウス変換 - naoya_t@hatenablog
の出番である。
Educational DP Contest / DP まとめコンテスト〈EDPC〉
1/6(日)20:00-25:00
始まった時点で家に帰る途中で20:14に参戦。
途中30分弱離席したけれど結局最後までやってて全26問中16完で172位
フル参加できてたら+1〜2問ってところか。
終わってから残りの問題にもひと通り目を通したけれどまだ習ってないテクが必要な問題がある。ぜひ今回持って帰りたい。
→ Educational DP Contest / DP まとめコンテスト〈EDPC〉補習篇(T,U,V,W,X,Y,Z) - naoya_t@hatenablog
ABC 114 Cを桁DPでも解いてみた
「桁DPで解きたくなる誘惑に負けず全探索で解くべき問題」ABC 114 Cを、後学のために桁DPでも解いてみたメモ。
(本番では3,5,7のみで出来た9桁までの数を全列挙しました)
桁DPのアイデアと実装については桁DP入門 - pekempey's blog がとても参考になります。
続きを読む【祝】DISCO presents ディスカバリーチャンネル コードコンテスト2019 予選【通過】
今年の本選にはコード部門に加え「装置実装部門」というのがあるらしく
なにそれ?
と思って参戦してみた
www.discoverychannel.jp
11/23(金祝) 21:00-22:30
いつもよりちょっと短い90分
(コンテストページはこちら)
4問目間に合わず3完110位…(22:38:44に4問目AC。あと10分あれば!)
1位〜109位までのお客様の中に2020年卒予定の学生さんが10人以上いらっしゃいましたら予選通過。
→通過しました。1/19(土)の本選「装置実装部門」でお会いしましょう。*1
〈蟻本拾い読み〉対称性のある数え上げ(p.268), スタックの利用(p.298)
蟻本拾い読み