bitDP
個人的に bitDP が苦手すぎるので過去問と自分の提出コードをまとめたサイトです
/icons/hr.icon
問題一覧
個人的に簡単なものから順に書いています
/icons/hr.icon
AOJ にある基本的な bitDP の問題、初めて履修する人はこれから始めると良いかも
うえきさんが書いた Qiita が個人的にはかなりわかりやすかった（自分はこれで bitDP を学んだ） /icons/hr.icon
水 diff の問題です、上の巡回セールスマン問題のコストが少し複雑なバージョンですが、やってみると勉強になると思います
/icons/hr.icon
緑 diff の bitDP です、上の問題で慣れたらこの問題にも挑戦してみると良いと思います
/icons/hr.icon
上記の ABC318-D とほぼ全く同じ問題です、復習がてらこちらも解いてみると良いと思います
yukicoder の昔の水 diff です
/icons/hr.icon
水 diff の問題です、面白い問題設定で解いていて楽しかったです
横棒をどの場合配置できるかを確認するのが高速化色々できそうで面白いです（高速化しなくても TL は余裕ですが）
/icons/hr.icon
水 diff 上位の問題です、制約が複雑でどう解けばいいのか考える必要があります
わかった時の閃きが最高でした
snuke さんの 公式解説動画 がかなりわかりやすかったです /icons/hr.icon
yukicoder の昔の水 diff、一捻りしているので学んだばかりの人にはちょうど挑戦し甲斐がある問題だと思います
/icons/hr.icon
青 diff です、トポロジカルソートの数え上げができる事をこの問題で初めて知りました
集合$ Sに対して、頂点$ vを追加する場合$ f(S) := \left\{ v から S - {v} へ向かう有向辺が存在しない \right\}と考えることができ、これを応用して数え上げることができます
/icons/hr.icon
緑 diff の問題です、想定解は前から貪欲に見ていくだけですが bitDP で解こうとすると途端に難易度が跳ね上がります
桁 dp っぽさが感じられた問題です
1 次元 ver.
/icons/hr.icon
yukicoder の青 diff、巡回セールスマン問題と似ていますが、少し捻りがあり難しいです
/icons/hr.icon
水 diff です、個人的にかなり苦手な問題です
考えなきゃ行けない状態は割と浮かびやすいですが、遷移でバグったり実装で苦労します
遷移するか否かの条件式で bitDP は和集合を考えることが多いというのに気付かされた問題です
/icons/hr.icon
CSES の問題
かなり難しいので大変、どういう状態を持つべきなのか、どの情報はいらないのか吟味するのが難しいです
自分の提出 ※第3者には見えないと思いますが、Python で 1ms のため、大半が TLE で落ちています... /icons/hr.icon
yukicoder の青 diff です
上記のエレベーターの問題と全く本質は同じです
入力の受け取り方を変えるだけで AC できます（笑）
/icons/hr.icon
青diff 上位です、自分は bitDP と知らされた状態で問題を解きましたが、全然分かりませんでした（解説 AC）。
かなり特殊な bitDP らしいなので自力で解けた方は本当にすごいです
/icons/hr.icon
ABC で出題された黄 diff、実装もクソ重いし何もわからん
未AC
/icons/hr.icon