AtCoder

ABC380 C問題(Move Segment)を解く

AtCoder_ABC380_C

AtCoder が提供しているABC(AtCoder Beginner Contest)380 C問題をC++で解いてみました。ABC380は、2024年11月16日21:00に実施されました。

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

C問題 Move Segment(Difficulty : 223)

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

ABC380 C問題 Move Segment

連長圧縮を行う自前ライブラリを利用しました。AtCoder Problems による Difficulty は 223 でした。

解答案

連長圧縮を行う自前ライブライを整備して持っていました。文字列を入力として、文字と繰り返し数を組にして返します。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++ プログラム例(ABC380C)

上記のライブラリを利用します。

文字を連長圧縮して、$K$ 回目に出現する ‘1’ の繰り返し回数を変数 tc に記憶しておきます。次に $K-1$ 回目に出現する ‘1’ の繰り返し数に tc を加えて ‘1’ を出力します。$K$ 回目に出現する ‘1’ は無視します。それ以外の場合は、そのまま出力します。

以下が、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()
{
	int n, k;
	cin >> n >> k;
	string s;
	cin >> s;

	vector<pair<char, int>> v = run_length_encoding(s);

	int tn = 0;
	int tc = 0;
	for (int i = 0; i < (int)v.size(); ++i) {
		if (v[i].first == '1') {
			++tn;
			if (tn == k) {
				tc = v[i].second;
			}
		}
	}

	string result;
	tn = 0;
	for (int i = 0; i < (int)v.size(); ++i) {
		if (v[i].first == '1') {
			++tn;
			if (tn == k - 1) {
				for (int j = 0; j < v[i].second + tc; ++j) {
					result += v[i].first;
				}
				continue;
			}
			if (tn == k) {
				continue;
			}
		}
		for (int j = 0; j < v[i].second; ++j) {
			result += v[i].first;
		}
	}

	cout << result << endl;

	return 0;
}

AC(Accepted=正しいプログラム)と判定されました。

Python でも連長圧縮のライブラリを整備しようとしましたが、十分な性能がでなかったため、Python 版プログラムの紹介を見送ります。

最後に

コンテストでは、31行目のローカル変数の初期化が抜けていて WA 判定をもらいました。コンパイラの警告には表示されていました。残念なミスです。

引き続き ABC の問題を紹介していきます。

COMMENT

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

CAPTCHA