Eは実質できていて、最後に間違いに気付き書き換えたものが間に合っていたら通っていました。うーん悔しい。
コンテスト後のツイート
E、通りました。最大値の初期化ミスでした。時間ギリギリで直せなかったのを直したら本当に通った。あと2秒あれば通ってたよ……。https://t.co/WNoDOGRb4a
— titia (@titia_til) December 24, 2021
赤はできるだけ葉に割り振りたい。それにより青が置ける個数をできるだけ減らす。深さ最大のものから消していく。青は全探索。
D. X(or)-mas Tree
解説AC。
考察が足りていなかった上、誤読もしていた。
木のpathに関する問題ということで（あと、STATUSを見たらPyPyでTLEが多く出ていたこともあり）、オイラーツアーとか、HL分解のようなことを考えてしまっていた。ちょっと苦手意識があるせいなのかね、こういう方面しか考えられなかったというのは。
が、そんなことは必要なかった。pathのxorだけを考えたいので、1～頂点xまでの累積xorをNODE[x]とすると、path u～v間のxorはNODE[u]^NODE[v]となる。これを使えば、エルフの条件も、uとvの間に辺を張ったものと解釈できる。
なので、後は、pathの距離が-1になっているものを後回しにしてDFS（つまり、01BFSみたいにする）していけば良い。
なお、誤読というのは、エルフに与えられるのが「距離を二進法にしたときの1の個数の2で割った余り」ではなく、単純に「距離を2で割った余り」だと思っていた、というものです。
これ、本番中実装してWAが出ていたら気付けなかった気がする……。
0 件のコメント:
コメントを投稿