AtCoder

ABC019 B問題(高橋くんと文字列圧縮)を解く

AtCoder_ABC019_B

AtCoder が提供しているABC(AtCoder Beginner Contest)019 B問題をC++で解いてみました。ABC019は、2015年2月28日21:00に実施されました。

AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。

B問題 高橋くんと文字列圧縮(Difficulty : 534(参考値))

問題の詳細は、リンク先をご覧ください。

ABC019 B問題 高橋くんと文字列圧縮

連長圧縮するだけです。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 の問題を紹介していきます。

COMMENT

メールアドレスが公開されることはありません。 が付いている欄は必須項目です

CAPTCHA