AtCoder が提供しているABC（AtCoder Beginner Contest）036 C問題をC++で解いてみました。ABC036は、2014年3月22日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
C問題 座圧（Difficulty : 956（参考値））
問題の詳細は、リンク先をご覧ください。
座標圧縮を行うだけです。AtCoder Problems による Difficulty は 956（参考値）でした。
解答案
この問題で、数列 $a_i$ を数列 $b_i$ に変換する操作を座標圧縮と呼びます。問題名「座圧」は座る面の圧力と座標圧縮という意味を重ねています。
問題文に記載されている座標圧縮の定義を以下に示します。
- $b_i$ はすべて非負整数である。
- $a_i < a_j$ ならば $b_i < b_j$ である。
- $a_i = a_j$ ならば $b_i = b_j$ である。
- 上の条件を満たす配列のうち、$b_i$ の最大値が最小となる。
これらの条件を満たす数列 $b$ を、数列 $a$ の座標圧縮の結果と呼びます。
C++ プログラム例（ABC036C）
座標圧縮の実装は「蟻本」（「プログラミングコンテストチャレンジブック」第2版 秋葉拓哉、岩田陽一、北川宣稔著、マイナビ 2012年）を参考にしました。
まず、数列 $a$ をソートし、重複を除去します。次に、各要素がこの新しい数列の中で何番目に位置するかを調べることで、座標圧縮の結果である数列 $b$ を得ることができます。
以下が、C++プログラムです。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
vector<int> sa(n);
sa = a;
sort(sa.begin(), sa.end());
sa.erase(unique(sa.begin(), sa.end()), sa.end());
for (int i = 0; i < n; ++i) {
int new_a = lower_bound(sa.begin(), sa.end(), a[i]) - sa.begin();
cout << new_a << endl;
}
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
最後に
座標圧縮は競技プログラミングで頻出する手法です。この記事を通じて、コードのテンプレートを整理することができました。
引き続き ABC の問題を紹介していきます。
