AtCoder ABC 213 C - Reorder Cards (茶色, 300 点)

一見いかめしい問題だけど、単に座標圧縮するかどうかだと気づけるかですね。

• 問題へのリンク

問題概要

のグリッドが与えられます。数 はそれぞれマス に書かれています。それ以外の マスには何も書かれていません。

このグリッドに対して、次の操作を可能な限り繰り返し行います。

• 数の書かれたカードを含まない行が存在するとき、その行のカードを全て取り除き、残りのカードを上へ詰める
• 数の書かれたカードを含まない列が存在するとき、その列のカードを全て取り除き、残りのカードを左へ詰める

操作が終了したとき、数が書かれたカードがそれぞれどこにあるか求めてください。なお、答えは操作の仕方に依らず一意に定まることが証明されます。

制約

• 
• 

整理する

問題内容がいかめしいけど、実はやるべきことはとても単純だ。たとえば マスが

(100, 674), (1, 76000), (50, 2), (10000, 16)

であった場合には、答えは

(3, 3), (1, 4), (2, 1), (4, 2)

になる。つまり、

• 座標方向の値：
• 座標方向の値：

のそれぞれ独立に、「それぞれの値が全体の中で何番目に小さい数か」を求めればよいということだ。これはまさに、座標圧縮に他ならない。座標圧縮については次の記事に詳しく書いた。

drken1215.hatenablog.com

今回は結局、2 つの数列について座標圧縮するだけなので、計算量は となる。

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
    // 入力
    int H, W, N;
    cin >> H >> W >> N;
    vector<int> X(N), Y(N);
    for (int i = 0; i < N; ++i) cin >> X[i] >> Y[i];

    // 座標圧縮の準備
    auto nX = X, nY = Y;
    sort(nX.begin(), nX.end());
    nX.erase(unique(nX.begin(), nX.end()), nX.end());
    sort(nY.begin(), nY.end());
    nY.erase(unique(nY.begin(), nY.end()), nY.end());

    // 座標圧縮
    for (int i = 0; i < N; ++i) {
        int xres = lower_bound(nX.begin(), nX.end(), X[i]) - nX.begin();
        int yres = lower_bound(nY.begin(), nY.end(), Y[i]) - nY.begin();
        cout << xres+1 << " " << yres+1 << endl;
    }
}