AtCoder が提供しているABC（AtCoder Beginner Contest）329 のC問題をC++とPythonで解いてみました。ABC329は、2023年11月18日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
C問題 Count xxx（Difficulty : 205）
問題はリンク先をご覧ください。
文字と連続する長さの組の種類をカウントします。AtCoder Problems による Difficulty は 205 でした。
解答案
C++ プログラム例（ABC329C）
最初に TLE（Time Limit Exceeded）判定となるプログラムを紹介します。以下は、補足とプログラムです。
- 同じ文字が続く限り、その文字列を set コンテナ result に格納します（16ー18行目）。
- 走査した文字が前の文字と異なれば、新しい文字だけの文字列として、文字列の走査を続けます（20ー22行目）。
- 最後にコンテナ result の要素数を出力します（26行目）。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin >> n;
string s;
cin >> s;
set<string> result;
string sub_s = "";
sub_s += s[0];
result.insert(sub_s);
for (int i = 1; i < n; ++i) {
if (s[i - 1] == s[i]) {
sub_s += s[i];
result.insert(sub_s);
} else {
sub_s = "";
sub_s += s[i];
result.insert(sub_s);
}
}
cout << result.size() << endl;
return 0;
}提出した結果は、23テストケースの内、4テストケースで TLE 判定でした（2023年11月19日の環境）。string 文字列を拡張するときにメモリを確保するなどの処理が発生するため、同じ文字が連続する文字列が長くなると、処理時間がかかるようです。
文字とその長さを組を set コンテナに格納すれば、計算量を減らせそうです。
- 同じ文字が続く限り、その文字と長さの pair を set コンテナ result に格納します（16ー18行目）。
- 走査した文字が前の文字と異なれば、新しい文字と長さ1の pair を格納して、文字列の走査を続けます（20ー22行目）。
- 最後にコンテナ result の要素数を出力します（26行目）。
以下のプログラムは AC（Accepted＝正しいプログラム）と判定されました。消費時間も最大で38msecでした（2023年11月19日の環境）。走査するオブジェクトの型を変えた効果がでました。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin >> n;
string s;
cin >> s;
set<pair<char, int>> result;
char ch = s[0];
int len = 1;
result.insert(make_pair(ch, len));
for (int i = 1; i < n; ++i) {
if (s[i - 1] == s[i]) {
++len;
result.insert(make_pair(ch, len));
} else {
ch = s[i];
len = 1;
result.insert(make_pair(ch, len));
}
}
cout << result.size() << endl;
return 0;
}Python プログラム例（ABC329C）
Python 版も基本的な考え方は同じです。以下となります。
"""AtCoder Beginner Contest 329 C"""
n = int(input())
s = input()
result = set()
ch = s[0]
length = 1
result.add((ch, length))
for i in range(1, n):
if s[i - 1] == s[i]:
length += 1
result.add((ch, length))
else:
ch = s[i]
length = 1
result.add((ch, length))
print(len(result))こちらも「AC」と判定されました。
最後に
コンテストでは、string の処理負荷に気付かず TLE 判定をもらいました。このような問題も、一発でACが取れればと思います。
引き続き ABC の問題を紹介していきます。
