ABC381 C問題（11/22 Substring）を解く

AtCoder が提供しているABC（AtCoder Beginner Contest）381 C問題をC++で解いてみました。ABC381は、2024年11月22日21:00に実施されました。

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

C問題 11/22 Substring（Difficulty : 209）

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

ABC381 C問題 11/22 Substring

文字列を連長圧縮して前準備しました。AtCoder Problems による Difficulty は 209 でした。

解答案

C++ プログラム例（ABC381C）

前処理として文字列を連長圧縮します。連長圧縮は自前で用意した関数を使います。制約により、文字列には ‘/’ が必ず含まれているため、解は1以上となります。

連長圧縮の結果の最初と最後を除いて、ループで調べます（33行目）。

• 前の要素が ‘1’ である。
• 今の要素が ‘/’ である。かつ個数が1個である。
• 後ろの要素が ‘2’ である。
• この場合、’1′ と ‘2’ の少ない方の個数に2を掛けて1を加えて解を更新します（コードの方が分かりやすいです。36行目をご覧ください）。

以下が、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;
	cin >> n;
	string s;
	cin >> s;

	auto p = run_length_encoding(s);
	int np = p.size();

	int result = 1;
	for (int i = 1; i < np - 1; ++i) {
		if ((p[i - 1].first == '1') && (p[i].first == '/') &&
			(p[i + 1].first == '2') && (p[i].second == 1)) {
			result = max(result, min(p[i - 1].second, p[i + 1].second) * 2 + 1);
		}
	}

	cout << result << endl;

	return 0;
}

AC（Accepted＝正しいプログラム）と判定されました。

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

最後に

コンテスト中は、条件「今の要素が ‘/’ である。かつ個数が1個である」に違反している場合でも解の候補としていました（2個以上あっても解になっていました）。わたし自身がこの間違いをしていました。今は、After-Contestの条件が追加されて、より正しく判定できるようになりました。

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