2016JOI春合宿1-1 Matryoshka 解説

問題リンク

解説

要素が複数あるクエリ問はとりあえず1要素ソートするのが基本。 たぶんどっちをソートしても解けるが、今回は直径を降順ソートした。 クエリとマトリョーシカの追加を合わせてソートすれば、直径についての条件を考える必要はなくなる。

次に、あるマトリョーシカを追加するとき、他のマトリョーシカの中に入れられれば入れてもよい、というのは少し考えるとわかる。 入れないという選択をするとき、代わりに入れる別のマトリョーシカと入れ替えても損をしないからである。

これで、他のマトリョーシカに入れていい、ということがわかったので、自分より高さが高いマトリョーシカの中で、他のマトリョーシカが中に入っていないものを選べればよい。 これは、高さの順でセグメントツリーで管理すればよい。

そして、答えを求めるときは、高さごとに「それ以下の高さのすでに追加されたマトリョーシカで、他のマトリョーシカが中に入っていないもの」の数を数えればよい。 追加の際、これらは高さの区間でしか変更がないため、ここもセグメントツリーで管理できる。Binary Indexed Tree を使うと楽である。

感想

これが春合宿本番で出たら、やるべきことをしっかり紙の上で整理することが求められるだろう。 デバッグの速さも重要である。