座標圧縮 Coordinate compression

方法

• 検索すれば豊富に見つかる

使いどころ

• 座標の範囲が10⁹などで走査したらTLEする
• 一方で座標データ数が10⁵などで座標圧縮したら間に合う

要素

• 配列・ソート
• 二分探索, lower_bound

それを使う問題たち

• Manhattan Crepe Cart (Google Code Jam)
  • https://codingcompetitions.withgoogle.com/codejam/round/0000000000051706/000000000012295c
• C - 陽気な妖姫 (AtCoder)
  • https://atcoder.jp/contests/iroha2019-day2/tasks/iroha2019_day2_c