はじめに
タイトルのままです。
今回から特定のアルゴリズム・データ構造・競プロのテクニックなどに焦点を当てながら、それを使用する問題を紹介していこうと思います！
第１弾は「bitDP」です
元記事は Scrapbox にまとめてあったのですが、Qiita に移植してみることにしました。
では早速本題に入っていきましょう
問題一覧
個人的に簡単と感じたものから順に書いています
AOJ DPL_2_A 巡回セールスマン問題
- AOJ にある基本的な bitDP の問題です。初めて履修する人はこれから始めるのがオススメです
- うえきさんが書いた PythonでbitDPを使い巡回セールスマン問題を解く が個人的にはとてもわかりやすかったです（自分はこれで bitDP を学びました）
- 自分の提出
ABC180 E - Traveling Salesman among Aerial Cities
- 水 diff の問題です
- 上の巡回セールスマン問題のコストが少し複雑なバージョンですが、やってみると勉強になると思います
- 自分の提出
第 13 回 日本情報オリンピック 予選 D - 部活のスケジュール表 (Schedule)
- 状態数が高々 $8$ 通りしかないため、遷移できるかどうかを bit 列で管理しながら dp で解くことが出来ます
- 個人的にはかなり基本的な bitDP に感じました
- 自分の提出
ABC318 D - General Weighted Max Matching
- 緑 diff の bitDP です、上の問題で慣れたらこの問題にも挑戦してみると良いと思います
- 入力の受け取り方があまり見かけないので苦戦しました（非本質）...
- 自分の提出
yukicoder No.698 ペアでチームを作ろう
- 上記の ABC318-D とほぼ全く同じ問題です、復習がてらこちらも解いてみると良いと思います
- yukicoder の昔の水 diff です
- 自分の提出
ABC113 D - Number of Amidakuji
- 水 diff の問題です、面白い問題設定で解いていて楽しかったです
- 横棒をどの場合配置できるかを確認するのが高速化色々できそうで面白いです（高速化しなくても TL は余裕ですが）
- 自分の提出（横棒の判定に O(W)）
- 自分の提出 (横棒の判定を bit 演算で高速化)
ABC142 E - Get Everything
yukicoder No.771 しおり
- yukicoder の昔の 水 diff です、一捻りしているので学んだばかりの人にはちょうど挑戦し甲斐がある問題だと思います
- 自分の提出
ABC041 🧪 D - 徒競走
- 青 diff です、トポロジカルソートの数え上げができる事をこの問題で初めて知りました
- 集合 $S$ に対して、頂点 $v$ を追加する場合、「$f(S) = v$ から $S - {v}$ へ向かう有向辺が存在しない」と考えることができ、これを応用して数え上げることができます
- こちらの解説記事 の漸化式の部分が個人的にはわかりやすかったです
- 自分の提出
ARC058 C - こだわり者いろはちゃん
- 緑 diff の問題です、想定解は前から貪欲に見ていくだけですが あえて bitDP で解こうとすると途端に難易度が跳ね上がります
- 桁 dp っぽさが感じられた問題です
- 自分の提出（2 次元 ver.）
- 自分の提出（1 次元 ver.）
yukicoder No.845 最長の切符
- yukicoder の青 diff です、巡回セールスマン問題と似ていますが、少し捻りがあり難しいです
- 自分の提出
ABC215 E - Chain Contestant
- 水 diff です、個人的にかなり苦手な問題です
- 考えなきゃ行けない状態は割と浮かびやすいですが、遷移でバグったり実装で苦労します
- 遷移するか否かの条件式で bitDP は和集合を考えることが多いというのに気付かされた問題です
- 自分の提出
CSES Problem Set Elevator Rides
- CSES の問題です、かなり難しいので大変、どういう状態を持つべきなのか、どの情報はいらないのか吟味するのが難しいです
-
自分の提出
- ※第3者には見えないと思いますが、Python で 1ms のため、大半が TLE で落ちています...
yukicoder No.733 分身並列コーディング
- yukicoder の青 diff です
- 上記のエレベーターの問題と全く本質は同じです
- 入力の受け取り方を変えるだけで AC できます（笑）
- 自分の提出
ABC310 F - Make 10 Again
- 青diff 上位です、自分は bitDP と知らされた状態で問題を解きましたが、全然分かりませんでした（解説 AC です）。
- かなり特殊な bitDP らしいなので自力で解けた方は本当にすごいです
- 自分の提出
ABC352 F - Estimate Order
- ABC で出題された 黄 diff です、実装もとても重いし何もわからないです
- 未AC