はまやんはまやんはまやん

hamayanhamayan's blog

Reorder Cards [AtCoder Beginner Contest 213 C]

https://atcoder.jp/contests/abc213/tasks/abc213_c

前提知識(というかそのもの)

  • 座標圧縮

解説

https://atcoder.jp/contests/abc213/submissions/24895309

今回の問題は座標圧縮という典型アルゴリズムの実装を要求されている。
座標圧縮を理解すれば、この問題はそれを使うだけで解くことができるので、
ググって理解してくることをオススメする。
…と書くと、書くことがなくなってしまうので、座標圧縮自体を今回は説明することにする。
解説にも相性があると思うので、以下が分からなかったら、適当に調べて色々見てみることを勧める。
先に書いておくと、図は作らないので、確実に他の記事の方が分かりやすい。

座標圧縮

座標圧縮が目標とすることは、2 4 7という数列に対して、小さい方から0,1,2と番号を振りなおす作業のことである。
よって2 4 7に対して「座標圧縮をする」と0 1 2と変換される。
4 1 9であれば1 0 2になるし、4 3 3 1なら2 1 1 0となる。
なんとなく何をしているかは分かると思うが、活用例が思いつかないと何のための操作か分からないかもしれない。

座標圧縮をどうやって実装するか

今まで2通りの実装方法を見たことがある。
ソートを使う方法とmap(連想配列)を使う方法であるが、今回はソートの方法でやってみる。

vector<int> ys;  
rep(i, 0, N) ys.push_back(A[i]);  
sort(all(ys));  
ys.erase(unique(all(ys)), ys.end());  
rep(i, 0, N) A[i] = lower_bound(all(ys), A[i]) - ys.begin();  

配列Aに対して座標圧縮を適用している。
まず、配列Aの要素の全てを1つの配列ysに移し替える。
次に移し替えた配列ysをソートして、unique関数とerase関数を組み合わせることで重複した要素を削除する。
これで、配列ysはソート済みで、かつ、配列Aに入っている数が重複なく入っている配列となる。
これがあればlower_boundを使って、あるA[i]が配列ysの何番目にあるかを高速に求めることができる。
そして、その何番目かという部分が座標圧縮後の値になっているので、それに置き換えていけば完了。
なお、座標圧縮前の数に戻したいときは配列ysを使えば、座標圧縮後のyは、座標圧縮前のys[y]となる。

さて…

この説明で座標圧縮が伝わっているといいのだが、これを使えば今回の問題は解ける。
今回の問題に戻ると、今回の問題は使われていない行や列を削除すると、最終的な座標はどうなりますか?という問題である。
これは0 4 90 1 2と変換されることを間を詰める、使われていない間の数を削除して詰めることとよく似ている。
というか同じことである。
そして、行と列の操作は互いに全く影響しない、もう少し具体的に言うと、列を1つ削除しても使われている行が使われなくなったり、
使われていない行が使われることは発生しない。
よって、行と列は独立に、それぞれ分けて変換しても問題ない。
なので、配列Aと配列Bに対して座標圧縮を行って1-indexedで答えれば答えとなる。

int H, W, N, A[101010], B[101010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> H >> W >> N;
    rep(i, 0, N) cin >> A[i] >> B[i];

    vector<int> ys;
    rep(i, 0, N) ys.push_back(A[i]);
    sort(all(ys));
    ys.erase(unique(all(ys)), ys.end());
    rep(i, 0, N) A[i] = lower_bound(all(ys), A[i]) - ys.begin();

    vector<int> xs;
    rep(i, 0, N) xs.push_back(B[i]);
    sort(all(xs));
    xs.erase(unique(all(xs)), xs.end());
    rep(i, 0, N) B[i] = lower_bound(all(xs), B[i]) - xs.begin();

    rep(i, 0, N) printf("%d %d\n", A[i] + 1, B[i] + 1);
}