Eまで五完。
順位表を見てGまで行ったが、Gは未履修で、思い付くのは不可能だったように思う。実装も非常に大変だった。
コンテスト後のツイート
E a人とN-a人に分けるとする。どちらにも入れない人がいる場合は双対セグメント木を使って除く。a人とN-a人が可能な人数を累積和で前計算しておくと、鶴亀算でどちらにでも入れていい人数が分かる。二項係数で計算。
— titia (@titia_til) April 11, 2026
F - Avoid Division
解説AC。
色数が多い色から葉を塗っていき、同じ色同士で塗られた葉の間のnodeにしるしをつけていく。それで全ての頂点にしるしが付けば良い……ということは分かった。重心みたいなことを考えるのかな……とは思ったが分からず。
重心みたいなものを考える、という部分は良かったが、その頂点＋葉を考え、その頂点を必ず通るように色を塗っていく、というのは思いつかなかった。
また、「重心みたいなもの」と書いたが、厳密には、その頂点に対する全ての部分木で葉の個数が全体の半分以下になるようなもの。そういう頂点は必ず存在する。
実装にも苦労したが、最後は変数の使い回しでWAになっていて、良くなかった。
G - Copy Query
解説AC。
永続セグメント木を初めて勉強し実装した。
遅延セグメント木などを理解していれば理解することは難しくないが、実装はかなり大変だった。
セグ木の値、各nodeの左側の子、右側の子、親、その区間の左端と右端、各Versionの根の値などを更新があるごとに追加していく。ちょっとTrie木のような実装を行った。
0 件のコメント:
コメントを投稿