Cまで三完でした。Dは難しかった。
D. Binary Spiders
いくつかの解法ツイートを見てAC。
まず、上位bitから考えていき、kのx bit目が0か1かで場合分けする。
0の場合は、「x bitが0の集合」「x bitが1の集合」という二つの問題に分割される。
kのx bit目が1の場合が問題。
x bit目が0のものと1のもの高々二つしか取れないが、全探索すると二乗になってしまう。
そこで、x bitが0のものを全探索することにし、もう片方はTrie木を使って整理する。x bit目が0の要素aに対して、できるだけa^uが大きくなるようなuをTrie木を利用して探していく。そのxorがk以上ならばそれを採用、そういう組が一つもなければ、何か一要素を適当に採用する。
Trie木を使い慣れていないこともあり、この解法は自力ではなかなか思いつけなかった気がする。自分のライブラリのTrie木が意外と使いやすかったのには驚いた。
0 件のコメント:
コメントを投稿