座標圧縮を学んだ(情オリ2008 ペンキEを解きました)
問題から
解法
まず, 与えられる座標がグリッドマスの座標ではなく, 座標平面上の格子点の座標であることに注意しましょう. これをグリッドのマスに変換するためには,
長方形左下の座標・・・そのまま
長方形右上の座標・・・それぞれ-1
をする必要があります.
ここから本題で, 制約をみるととても二次元配列にお絵かきをすることはできそうにありません.
そこで, 与えられる長方形の数が小さいことを利用します. 長方形の端点の座標さえわかっていれば, その他の何もない場所を省くことができます.
そこで, まずx方向について,
- 長方形の左端とその左側の縦軸
- 長方形の右端とその右側の縦軸
これを記憶しておけば, 情報としては十分になります. y座標については
- 長方形の上端とその上側の横軸
- 長方形の下端とその下側の横軸
を記憶しておけば十分です.
また, 盤面の端点も記憶しておく必要があります.
このようにしてまず, 圧縮の際に残す軸を決定します.
これをvectorにいれてソートし, 重複を除きます.
ソートするというのがポイントで, この座標圧縮において, この時点で長方形の各点の座標の位置関係（大小関係）は保存されます.
この大小関係の保存を利用して, 記憶したvectorから,
座標圧縮後の長方形の各端点の座標を復元することができます.
これをx,y座標それぞれにおいて実行すると, あとは連結成分の数え上げの問題となるので, DFSをすると答えが得られます.
それでもなかなかグリッドは大きいので, imos法などを使ってグリッドを埋めると時間的には安全です.
提出
Submission #3440558 - 第７回日本情報オリンピック 本選（オンライン） | AtCoder
(再帰だとMLEしそうだと思って再帰を使わずに書いたらqueueに突っ込んでいて, BFSしちゃってます)
感想
昔蟻本で読んだときはソースコードの意味がわからなかったんですけど, 今読むとわかって成長を感じました.
