Baby Stepsなブログ

競プロとか。間違ったこと書いてあったら@pi0nep1oneにご連絡ください。

座標圧縮に関する解説と練習問題

競技プログラミング ライブラリ アルゴリズム

前提

一次元座標圧縮はBITによる転倒数の数え上げでお馴染み。

二次元の場合は、x軸、y軸を独立に捉えることでほぼ同様に求めることができる。

二次元座標圧縮における注意点は、登場する座標の1つ隣の座標も登録する点にある。これは登場する座標だけで圧縮を行うと、元のグリッドの線分（や長方形）間に存在した空白を潰してしまう可能性があるため。（この図解が参考1のスライドにある）

座標圧縮の基本的な実装

  • パラメータに渡した座標をmutableに扱い、圧縮後の座標に置き換える
    • 座標圧縮が必要になる問題は、線分の始点と終点や長方形（3Dなら直方体）の対角など、同数の2つの座標が与えられる形式が多く、そのため引数に2つのリストを取るようにすると便利なことが多い（練習問題での compress の呼び出し元を参照）
  • 戻り値として、引数に渡した座標（とその1つ隣の座標）の圧縮前の座標をソートし重複を排除したリストvalsを返す

上記の様にすることで、圧縮後の値xから圧縮前の値を復元したい場合、vals[x] と記述するだけで簡単に行うことができる。

実際の使い方は以下の練習問題の解法を参照。

template<typename T>
vector<T> compress(vector<T> &v1, vector<T> &v2){
  vector<T> vals;
  int n = v1.size();
  for(int i=0; i<n; i++){
    for(int j=0; j<=1; j++){
      vals.push_back(v1[i]+j);
      vals.push_back(v2[i]+j);
    }
  }
  sort(vals.begin(), vals.end());
  vals.erase(unique(vals.begin(), vals.end()), vals.end());
  for(int i=0; i<n; i++){
    v1[i] = lower_bound(vals.begin(), vals.end(), v1[i]) - vals.begin();
    v2[i] = lower_bound(vals.begin(), vals.end(), v2[i]) - vals.begin();
  }
  return vals;
}

練習問題

座標圧縮が必要になる問題では、座標圧縮を行い、imos法により圧縮後の座標をグリッドにマッピングするという処理を書くことが多い。（そのため、ここでは多次元imos法の書き方を知っていることを前提とする）

そして以下の様なことを問う問題が多い。

  1. 座標平面と長方形が与えられて、長方形が重なる領域の面積の総和はいくつか？（三次元の問題もある）
  2. 座標平面と線分が与えられて、線分で区切られた領域の数はいくつか？
二次元座標圧縮

https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_4_A&lang=ja

問題形式1の問題で、圧縮した座標をグリッドにマッピングし、そのグリッドの1マス1マスの面積を求め、その総和を求めることで解を求めている。

signed main()
{
  int n; cin>>n;
  vector<long long> x1(n), y1(n), x2(n), y2(n);
  for(int i=0; i<n; i++) cin>>x1[i]>>y1[i]>>x2[i]>>y2[i];
  
  vector<long long> X = compress(x1, x2);
  vector<long long> Y = compress(y1, y2);
  
  int h = Y.size(), w = X.size();
  vector<vector<int>> G(h, vector<int>(w));
  
  // 二次元imos
  for(int i=0; i<n; i++){
    G[y1[i]][x1[i]]++;
    G[y2[i]][x2[i]]++;
    G[y1[i]][x2[i]]--;
    G[y2[i]][x1[i]]--;
  }
  for(int i=0; i<h-1; i++){
    for(int j=0; j<w; j++){
      G[i+1][j] += G[i][j];
    }
  }
  for(int i=0; i<h; i++){
    for(int j=0; j<w-1; j++){
      G[i][j+1] += G[i][j];
    }
  }
  
  // グリッドにおける各セルの面積の総和を求めることで解を得る
  long long ans=0;
  for(int i=0; i<h; i++){
    for(int j=0; j<w; j++){
      if(G[i][j]>0){
        ans += (Y[i+1]-Y[i]) * (X[j+1]-X[j]);
      }
    }
  }
  cout<<ans<<endl;
}

atcoder.jp

問題形式2の問題。座標圧縮したグリッドに対してBFSを行い、その回数が解となる。

この問題では圧縮する座標にグリッドの両端を加えるため、引数に head, tail を追加している。

#define rep(i, n) for (long long i = (long long)(0); i < (long long)(n); ++i)
template<class t> using vc=vector<t>;

template <typename T>
vector<T> compress(vector<T> &v1, vector<T> &v2, T head, T tail) {
  vector<T> vals;
  int n = v1.size();
  for (int i = 0; i < n; i++) {
    vals.push_back(v1[i]);
    vals.push_back(v2[i]);
    if(v2[i] + 1 <= tail) vals.push_back(v2[i] + 1);
  }
  vals.push_back(head);
  vals.push_back(tail);
  sort(vals.begin(), vals.end());
  vals.erase(unique(vals.begin(), vals.end()), vals.end());
  for (int i = 0; i < n; i++) {
    v1[i] = lower_bound(vals.begin(), vals.end(), v1[i]) - vals.begin();
    v2[i] = lower_bound(vals.begin(), vals.end(), v2[i]) - vals.begin();
  }
  return vals;
}

const int dy[] = {0, 1, 0, -1};
const int dx[] = {1, 0, -1, 0};

inline bool inside(int y, int x, int H, int W) {
    return (y >= 0 && x >= 0 && y < H && x < W);
}

signed main()
{
  cin.tie( 0 ); ios::sync_with_stdio( false );
  
  int H,W; cin>>H>>W;
  int n; cin>>n;
  vc<int> x1(n),y1(n),x2(n),y2(n);
  rep(i,n) cin>>x1[i]>>y1[i]>>x2[i]>>y2[i];
  
  auto X=compress(x1,x2,0,H);
  auto Y=compress(y1,y2,0,W);
  
  int h=X.size(), w=Y.size();
  vc<vc<int>> G(h, vc<int>(w));
  
  // 二次元imos
  rep(i,n){
    G[x1[i]][y1[i]]++;
    G[x1[i]][y2[i]]--;
    G[x2[i]][y1[i]]--;
    G[x2[i]][y2[i]]++;
  }
  rep(i,h){
    rep(j,w-1){
      G[i][j+1]+=G[i][j];
    }
  }
  rep(j,w){
    rep(i,h-1){
      G[i+1][j]+=G[i][j];
    }
  }

  h--, w--;
  
  // BFS
  int ans=0;
  rep(i,h){
    rep(j,w){
      if(G[i][j]==0){
        ans++;
        queue<pair<int,int>> q;
        q.emplace(i,j);
        G[i][j]=1;
        while(!q.empty()){
          int x,y; tie(x,y)=q.front(); q.pop();
          rep(k,4){
            int nx=x+dx[k], ny=y+dy[k];
            if(inside(nx,ny,h,w) and G[nx][ny]==0){
              G[nx][ny]=1;
              q.emplace(nx,ny);
            }
          }
        }
      }
    }
  }
  cout<<ans<<endl;
}
三次元座標圧縮

atcoder.jp

これも問題形式1の問題で三次元に拡張したもの。（三次元imos法の書き方の練習にもなる）

#define rep(i, n) for (long long i = (long long)(0); i < (long long)(n); ++i)
using ll = long long;
template<class t> using vc=vector<t>;

signed main()
{
  cin.tie( 0 ); ios::sync_with_stdio( false );
  
  int n,K; cin>>n>>K;
  vc<ll> x1(n), y1(n), z1(n), x2(n), y2(n), z2(n);
  rep(i,n){
    cin>>x1[i]>>y1[i]>>z1[i]>>x2[i]>>y2[i]>>z2[i];
  }
  vc<ll> X=compress(x1,x2);
  vc<ll> Y=compress(y1,y2);
  vc<ll> Z=compress(z1,z2);
  int h=X.size(), w=Y.size(), d=Z.size();
  vc<vc<vc<ll>>> G(h, vc<vc<ll>>(w, vc<ll>(d)));
  
  // 三次元imos
  rep(i,n){
    G[x1[i]][y1[i]][z1[i]]++;
    G[x1[i]][y2[i]][z1[i]]--;
    G[x1[i]][y1[i]][z2[i]]--;
    G[x2[i]][y1[i]][z1[i]]--;
    G[x1[i]][y2[i]][z2[i]]++;
    G[x2[i]][y1[i]][z2[i]]++;
    G[x2[i]][y2[i]][z1[i]]++;
    G[x2[i]][y2[i]][z2[i]]--;
  }
  rep(i,h){
    rep(j,w){
      rep(k,d-1){
        G[i][j][k+1]+=G[i][j][k];
      }
    }
  }
  rep(i,h){
    rep(k,d){
      rep(j,w-1){
        G[i][j+1][k]+=G[i][j][k];
      }
    }
  }
  rep(k,d){
    rep(j,w){
      rep(i,h-1){
        G[i+1][j][k]+=G[i][j][k];
      }
    }
  }
  
  ll ans=0;
  rep(i,h){
    rep(j,w){
      rep(k,d){
        if(G[i][j][k]>=K){
          ans+=(X[i+1]-X[i])*(Y[j+1]-Y[j])*(Z[k+1]-Z[k]);
        }
      }
    }
  }
  cout<<ans<<endl;
}

参考

参考1）

www.slideshare.net

参考2）実装を参考にさせていただきました。

algo-logic.info