AtCoder が提供しているABC（AtCoder Beginner Contest）019 B問題をC++で解いてみました。ABC019は、2015年2月28日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
B問題 高橋くんと文字列圧縮（Difficulty : 534（参考値））
問題の詳細は、リンク先をご覧ください。
連長圧縮するだけです。AtCoder Problems による Difficulty は 534（参考値）でした。
解答案
問題文で連長圧縮について説明しています。
入力例2）aabbbbbbbbbbbbxyza → a2b12x1y1z1a1
18文字の文字列を13文字に変換できています。同じ要素が続く場合、圧縮の効率が高くなります。ただし、入力例3のように元の文字列より長くなることもあります。
連長圧縮を行う関数を別に実装します。
- 入力：連長圧縮する文字列
- 戻り値：連長圧縮した結果、文字と繰り返し数を組にした vector コンテナ
CおよびC++の文字列は、末尾に文字 ‘\0’ を持つことを前提としています。
vector<pair<char, int>> run_length_encoding(string s)
{
vector<pair<char, int>> result;
int index = 0;
while (index < (int)s.length()) {
char ch = s[index];
int count = 1;
while (ch == s[index + 1]) {
++index;
++count;
}
result.push_back(make_pair(ch, count));
++index;
}
return result;
}C++ プログラム例（ABC019B）
この問題自体が連長圧縮のテストに使えます。
入力の文字列を上記関数に与えて、その結果を表示します。以下が、C++プログラムです。
#include <bits/stdc++.h>
using namespace std;
vector<pair<char, int>> run_length_encoding(string s)
{
vector<pair<char, int>> result;
int index = 0;
while (index < (int)s.length()) {
char ch = s[index];
int count = 1;
while (ch == s[index + 1]) {
++index;
++count;
}
result.push_back(make_pair(ch, count));
++index;
}
return result;
}
int main()
{
string s;
cin >> s;
vector<pair<char, int>> result = run_length_encoding(s);
int n = (int)result.size();
for (int i = 0; i < n; ++i) {
cout << result[i].first << result[i].second;
}
cout << endl;
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
最後に
ABC380C（解説記事）で連長圧縮の自前ライブラリについて解説しました。ライブラリのテストのために解いた問題を紹介しました。
引き続き ABC の問題を紹介していきます。
