AtCoder が提供しているABC（AtCoder Beginner Contest）380 C問題をC++で解いてみました。ABC380は、2024年11月16日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
C問題 Move Segment（Difficulty : 223）
問題の詳細は、リンク先をご覧ください。
連長圧縮を行う自前ライブラリを利用しました。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 の問題を紹介していきます。
