けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 113 C - ID (300 点) (座標圧縮の教育的練習問題)

いわゆる「座標圧縮」を練習できる問題!!!

問題へのリンク

問題概要

 M 組の 2 整数  (P_i, Y_i) が与えられる。 P_i の値は  1, 2, \dots, N のいずれかである。

 i に対して、 Y_i という値が、 P の値が等しいようなものの中で何番目に小さい値なのかを求めよ。
(出力形式については特殊なので、元問題を参照)

制約

  •  1 \le N, M \le 10^{5}
  •  Y_i はすべて互いに相異なる

座標圧縮とは

まさに「座標圧縮」をしなさい、という問題!!!

座標圧縮とは、例えば

8, 100, 33, 12, 6, 1211

のような数値があったときに、それぞれの数値に対して、それが何番目に小さい数値なのかを割り振る作業。下のようになる。

1, 4, 3, 2, 0, 5

なお注意点として、今回の問題では要求されないが、同じ値については同じ番号をつける。例えば

6, 9, 9, 2, 100

に対しては

1, 2, 2, 0, 3

という風になる。

座標圧縮のやり方

まず数の候補をすべて列挙した vector を作ります

vector<int> vals;
for (int i = 0; i < n; ++i) vals.push_back(a[i]);

という感じです。a を座標圧縮したい配列だとします。次に vals をソートします。

sort(vals.begin(), vals.end());

このままでは値が重複してしまっている可能性があるので、重複を除きます (今回の問題では  Y_i が異なることが保証されているので不要ですが...)

vals.erase(unique(vals.begin(), vals.end()), vals.end());

これで準備完了です。あとはおなじみの「整列済みの配列に対して各値がどこにあるかを二分探索して求める」というのをやればよいです。C++ では lower_bound() を使えます。

for (int i = 0; i < N; ++i) {
  int id = lower_bound(vals.begin(), vals.end(), a[i]) - vals.begin();
}

という感じです。lower_bound() によって求められるのは vals.begin() からどれだけ進んだかを表すイテレーターなので、vals.begin() を引くことで丁度求めたい値を求めることができます。

今回の問題

今回の問題でもちょっと複雑になっただけでやりたいことは座標圧縮です。

  •  P_i の値ごとに  Y_i たちをまとめてあげて、それぞれについて座標圧縮する

とすることで解くことができます。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    // 入力
    int n, m; cin >> n >> m;
    vector<int> P(m), Y(m);
    for (int i = 0; i < m; ++i) cin >> P[i] >> Y[i], --P[i];
    
    // vals[v] := P[i] = v であるような i についての Y[i] の値を集めたもの
    vector<vector<int> > vals(n);
    for (int i = 0; i < m; ++i) vals[P[i]].push_back(Y[i]);
    
    // 各 p の値に対して
    for (int v = 0; v < n; ++v) {
        sort(vals[v].begin(), vals[v].end());
        
        // 今回は不要だが、通常は数のダブりをなくす
        vals[v].erase(unique(vals[v].begin(), vals[v].end()), vals[v].end());
    }

    // 答え
    for (int i = 0; i < m; ++i) {
        int v = P[i];
        printf("%06d", v + 1);
        
        // 座標圧縮して導いた答え
        int id = lower_bound(vals[v].begin(), vals[v].end(), Y[i]) - vals[v].begin();
        printf("%06d\n", id + 1);
    }
}