読者です 読者をやめる 読者になる 読者になる

はまやんはまやんはまやん

hamayanhamayan's blog

競技プログラミングにおけるマージテク問題まとめ

間違っていたら指摘して頂けると助かります。

マージテクとは?

集合をまとめる時に大きい方に小さい方を移動させることでマージさせることです。
小さい方にしっかりまとめることで処理時間とメモリを節約できて、間に合うというやつです。
マージにかかる時間がならしlognになるとマージテク発祥の地らしき所に書いてあります。
https://topcoder.g.hatena.ne.jp/iwiwi/20131226/1388062106
正式名称は「データ構造をマージする一般的なテク」だそうです。
https://www50.atwiki.jp/joioi/m/pages/32.html#id_eb75c48d

問題

Codeforces Round #396 (Div. 2) D. Mahmoud and a Dictionary

http://codeforces.com/contest/766/problem/D?csrf_token=202bf974dbe7cd374c305230989ca14d
一発でマージテクかな?と思った問題。
初めてマージテクを試したら間に合った。
小さい方に移さないでやってみるとMLEした。

AGC014 E. Blue and Red Tree

http://agc014.contest.atcoder.jp/tasks/agc014_e
ぱっと見て、マージテクに見えないが、考察するとマージテク。