drken1215 https://blog.hatena.ne.jp/drken1215/ けんちょんの競プロ精進記録 https://drken1215.hatenablog.com/ AOJ OUPC 有志コン XOR BinaryTrie trie木 半分全列挙 N個のペア値の問題 DP状態:smaller(桁DP) 再帰的に上位桁から順に値で分類した木を作る 0と1の問題 データ構造 制約条件:総和<=K どの場所で初めてsmallerになるかを考える DP状態:どの桁まで見たか(広義の桁DP) 大学コンテスト 半分全列挙 + Binary Trie！！ あるいは、Binary Trie 自体を意識しなくても、上の位から順に桁 DP 的発想で考えていると、それが自然に Binary Trie 上の探索そのものとみなせる！ すごくいい Binary Trie の経験になった！！ 問題へのリンク editorial 問題概要 2 組の 個の整数 、 が与えられる ( は 0 以上)。 の部分集合 であって、 の XOR 和が 以下であるもののうち、 の最大値を求めよ。 制約 考えたこと 見た目はいかにも半分全列挙！！！ 半分全列挙することを考えると、次のような処理を高速にこなせるデータ構造を設計したくなる… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fdrken1215.hatenablog.com%2Fentry%2F2020%2F12%2F13%2F030800" title="AOJ 3213 Xor Mart (OUPC 2020 E) - けんちょんの競プロ精進記録" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://cdn.user.blog.st-hatena.com/default_entry_og_image/80936665/1516148889515660 Hatena Blog https://hatena.blog 2020-12-13 03:08:00 rich https://drken1215.hatenablog.com/entry/2020/12/13/030800 1.0 100%