Eまで五完。
順位表を見てGまで行ったが、Gは未履修で、思い付くのは不可能だったように思う。実装も非常に大変だった。
コンテスト後のツイート
E a人とN-a人に分けるとする。どちらにも入れない人がいる場合は双対セグメント木を使って除く。a人とN-a人が可能な人数を累積和で前計算しておくと、鶴亀算でどちらにでも入れていい人数が分かる。二項係数で計算。
— titia (@titia_til) April 11, 2026
G - Copy Query
解説AC。
永続セグメント木を初めて勉強し実装した。
遅延セグメント木などを理解していれば理解することは難しくないが、実装はかなり大変だった。
セグ木の値、各nodeの左側の子、右側の子、親、その区間の左端と右端、各Versionの根の値などを更新があるごとに追加していく。ちょっとTrie木のような実装を行った。
0 件のコメント:
コメントを投稿