Aizu Online Judge(AOJ)の「データの集合とクエリ処理(DSL)」のコースを制覇した。

AOJの「データの集合とクエリ処理(DSL)」のコースをC言語で制覇した。

DSL全制覇！

問題	解答例
DSL_1_A 互いに素な集合	Union Find木
DSL_1_B 重み付きUnion Find木	重み付きUnion Find木
DSL_2_A Range Minimum Query(RMQ)	セグメント木
DSL_2_B Range Sum Query(RSQ)	セグメント木
DSL_2_C 領域探索（kD 木）	X軸とY軸で二分探索
DSL_2_D Range Update Query(RUQ)	更新時間も含めてセグメント木にする
DSL_2_E Range Add Query(RAQ)	セグメント木
DSL_2_F RMQ and RUQ	遅延評価セグメント木
DSL_2_G RSQ and RAQ	遅延評価セグメント木
DSL_2_H RMQ and RAQ	遅延評価セグメント木
DSL_2_I RSQ and RUQ	遅延評価セグメント木
DSL_3_A The Smallest Window I	尺取法
DSL_3_B The Smallest Window II	尺取法
DSL_3_C The Number of Windows	尺取法
DSL_3_D Sliding Minimum Element(スライド最小値)	deque, (二分探索) or セグメント木(RMQ)
DSL_4_A Union of Rectangles	座標圧縮, いもす法
DSL_5_A The Maximum Number of Customers	いもす法
DSL_5_B The Maximum Number of Overlaps	いもす法

重み付きUnion Find

https://qiita.com/drken/items/cce6fc5c579051e64fab に詳しい解説がある。数値の大小とUnion Findの矢印の向きが少しややこしい。

セグメント木/遅延評価セグメント木

https://cstmize.hatenablog.jp/entry/2020/05/21/%E3%82%BB%E3%82%B0%E3%83%A1%E3%83%B3%E3%83%88%E6%9C%A8/%E9%81%85%E5%BB%B6%E8%A9%95%E4%BE%A1%E3%82%BB%E3%82%B0%E3%83%A1%E3%83%B3%E3%83%88%E6%9C%A8%E3%81%AE%E5%AE%9F%E8%A3%85%E3%81%AE%E3%82%B3%E3%83%84 にセグメント木/遅延評価セグメント木の実装のコツを書いた

尺取法

https://cstmize.hatenablog.jp/entry/2020/05/21/%E3%81%97%E3%82%83%E3%81%8F%E3%81%A8%E3%82%8A%E6%B3%95%E3%81%AE%E5%AE%9F%E8%A3%85%E3%81%AE%E3%82%B3%E3%83%84 に尺取法の実装のコツを書いた

いもす法

いもす法は入力を1次差分(もしくはn次差分)の情報と解釈し、積分してもとに復元することで計算量を落とす手法。本家の解説はここ

https://qiita.com/e869120/items/eb50fdaece12be418faa#%E7%B4%AF%E7%A9%8D%E5%92%8C-1 に例題があって、解答はここ。

座標圧縮

座標圧縮は半開区間[a, b)があって、点a, bをメモ -> 大小関係を保存しつつ数値を小さくする技術。仰々しい名前がついているが単にmap<int(大), int(小)>で変換するだけ。別にmap[int(小)] => int(大)という配列を持てばもとの値を復元できる。

https://qiita.com/e869120/items/acba3dd8649d913102b5#%E5%BA%A7%E6%A8%99%E5%9C%A7%E7%B8%AE とか、蟻本の中級編を見ると良い。蟻本では6点メモするみたいなことが書いてあるが、実は2点をメモするだけで十分だったりする。

その他

• スライド最小値はdequeというデータ構造を使うのが模範解答(といってもqueueに毛が生えたもので大したものではない)だが、セグメント木でも実装できる。

• kD木の問題はX軸とY軸で独立に二分探索することで制限時間に間に合ったのでこれでいいや。

• これでも解けるぜ、っていうのがあったら教えて下さいm( )m