AtCoder ABC 113 C - ID (緑色, 300 点)

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

問題へのリンク

問題概要

組の 2 整数 が与えられる。 の値は のいずれかである。

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

制約

• 
• はすべて互いに相異なる

座標圧縮とは

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

座標圧縮とは、例えば

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());

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

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() を引くことで丁度求めたい値を求めることができます。

今回の問題

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

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

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

#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);
    }
}