LoginSignup
0
0

【Python】座標圧縮ライブラリをつくろう

Last updated at Posted at 2023-12-20

座標圧縮は頻出ですが、値の復元はなんとなく億劫になりがちなのでもろもろライブラリ化しました。

1 次元の場合

class Compress:
  def __init__(self, arr):
    values = sorted(set(arr))
    self.translator = dict([(values[i], i) for i in range(len(values))])
    self.inv_translator = values

  def to_comp(self, x):
    return self.translator[x]

  def from_comp(self, v):
    return self.inv_translator[v]

to_comp: arr に登場する値を入れると、圧縮後の値が返ってくる
from_comp: 圧縮後の値を入れると、対応する arr の値が返ってくる

点列の圧縮から、多次元座標列の圧縮に拡張することもできます。

2 次元の場合

class Compress2D:
  def __init__(self, arr):
    self.x = Compress([x for x, y in arr])
    self.y = Compress([y for x, y in arr])

  def to_comp(self, x):
    return (self.x.translator[x[0]], self.y.translator[x[1]])

  def from_comp(self, v):
    return (self.x.translator[v[0]], self.y.translator[v[1]])

2 次元座標列が与えられた時、それぞれの座標軸で圧縮を行います。

to_comp: arr に登場する座標を入れると、圧縮後の座標が返ってくる
from_comp: 圧縮後の座標を入れると、対応する arr の座標が返ってくる

例題

ネタバレ 二次元の座標圧縮を行う

https://atcoder.jp/contests/abc168/tasks/abc168_f

おわり

座標圧縮してセグ木に載せてまた戻すところまでをライブラリに

0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
0
0