bitDP

atcoder.jp・参考 Editorial - THIRD PROGRAMMING CONTEST 2023 ALGO（AtCoder Beginner Contest 318） 「bitDPで巡回セールスマンを解く」の解説がよくわからなかったのでさらに解説【python実装】 - Qiita bitDP（集合を用いたDP）について - D言語で競プロ ・説明 参考記事の1つ目をPythonで実装した。この問題はbitDPを使って解く。bitDPについては参考記事2，3を参考にした。 集合bに含まれていない頂点を追加してDPを更新していく。コードの説明は下の実装でコメントアウトしている。 …

ec ABC317C 解法1: BitDP ハミルトン閉路と同様に， 状態 \(\,(s,v)\,\) の 2つ を持って遷移． ここで，\(s \in 2^{N}\) は訪れた頂点の集合， \(v \in s\) は最後に訪れた頂点． 試験中はこの方針で考えていた． しかし，\(s\) しか状態に持っていなかったため WA. 例を作ることで，間違いを納得しやすかった． Star 型の tree を作って確認した． 例を作るのは，ソースコードを眺めるよりも早く解決する場合も多い． 急がば回れとも言える． 間違いを特定しやすい例を構築する能力は重要． 極端すぎず，暗算が出来る例． また，WA に…

ABC199E BitDP. 順列を決めていくが，次を決めるときに， 今まで選んだ元の集合が分かっていれば，選んだ順番は無関係． 実装\(M\) 個の条件を調べる． 数え上げるとき，常に条件を満たしている様にとっている． つまり，\(s \in 2^{N}\) を調べ終わっていて， \(i in N\) s.t. \(i \not\in s\) に対して \(t := s \cup \{i\}\) のケースを調べるとき， \(s\) は条件を満たしている． 先頭\(x\) 個を見たとき，\(y\) 以下の個数が \(z\) 以下であるかを判定したい． \(\vert t \vert > x \…

ABC215E BitDP. 今調べている \(i \in N\) に対して，コンテストに参加出来るかどうかは， 次の2つが分かっているれば十分． 今まで参加したことのあるコンテストの集合 最後に参加したコンテスト 実装:10種類のコンテストがあるが， まだ 1回もコンテストに参加していない場合は，形式的に 11種類目のコンテストに参加したことにする． 使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925" int main() { ll n; cin >> n; string s; cin >> s; ll…

ARC132C まず，愚直なDPを考えると， \(dp_{i,s} := \) \([0,i)\) まで,使った数のset \(s \in 2^{N}\). これは TLE, MLE. 改良を考える． \(i \in N\) は減らすのが難しいので， \(s \in 2^{N}\) を減らすことを考える． 与えられた条件から，任意の \(i \in N\) に対して， \(- d \leq p_{i} - i \leq d\). よって， \(p_{i}\) の候補は \(2d+1\) 通りに絞れる． したがって，状態が \(O(2^{2d+1})\). 遷移は \(O(N)\). 使っている…

考えてみれば当然だけど、何回かやらかしているので自戒を込めて 本記事には以下の問題のネタバレが含まれます。 競プロ典型90問 45日目 Simple Grouping（★6） TL; DR メモ化再帰で初期値から更新されない値がある場合、メモ化配列を探索済みとして更新する処理を入れる。 例題 競プロ典型90問 45日目 Simple Grouping（★6） ユークリッド平面上に、N個の点 (X1, Y1), (X2, Y2), ⋯, (XN ,YN)があります。 これらを、次の条件を満たすようにK個のグループに分けることを考えます。 ・複数のグループに入る点があってはならない。 ・どのグルー…