ABCEの四完で約半年ぶりにHighestを更新したものの、後でEが嘘だったことが発覚。まぁ、そんなものか。
D - XOR Game
ちょっと考えて、トライ木を使うのでは？ と思ったところで手が止まってしまったのは良くない。トライ木の理解が不足していたのが敗因だと思うので、ちゃんと復習しておかないと。
……と思ったが、トライ木を使わなくても再帰を使えばACできると目にし、そちらの方法でAC。（トライ木の復習はしていません）
Aの全ての要素を二つずつペアにし、それらのxorの最大値を取る……という問題を考えたとき、それができるだけ小さくなるようなペアの取り方を考える問題だ、ということはすぐに気付けた。
問題は、どう実装するか。
上位bitから見て行って、立っているbitが偶数個なら、立っているもの同士、立っていないもの同士をペアにすれば良い。それは再帰で書ける。
立っているbitが奇数個だったときは、bitが立っているもの（それらの集合をBとする）と立っていないもの（Cとする）とのxorを取らなければならない（ので、答えのそのbitは必ず立つことになる）。そのようなペアのうち、最小のものを探せば良い。
……ということは分かるが、この実装が悩ましい。これをTrie木を使って処理するというのが公式解説の方法だった。
だがこれも上位bitから見ていく方法でできる。
奇数個立っていたbitの次のbitを考える。
BとCの両方でそのbitが立っているものがある、もしくは、両方でそのbitが立っていないものがある、のなら、立っているもの同士、もしくは立っていないもの同士のペアを取った方が良い。そのいずれかの最小値が答えになる（ので、再帰が回る）。
そういうものがなければ、答えにおいて今考えたbitも立っていることが分かる。そして、その次のbitを見ることになる。
E - Increasing LCMs
前から素因数の要素数が少ない順に追加していけば良いと思いACしたけれど、嘘でした。
本当の解法である「後ろから決定していく」というのも一応考えていたので、WAが出ていたら方針転換できた可能性はある。
けれど、提出したときは結構自信を持っていた（証明できた気がしていた）ので、動揺したと思う。残り二十分ほど、そんな状態で方針転換してACまでいけたか、というと……。実際のところは分かりませんね。
（Fもいずれ解きたい）
0 件のコメント:
コメントを投稿