AtCoder が提供しているABC（AtCoder Beginner Contest）342 のC問題をC++とPythonで解いてみました。ABC342は、2024年2月24日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
C問題 Many Replacement（Difficulty : 505）
問題はリンク先をご覧ください。
クエリで文字の変換テーブルを更新して、後でまとめて変換します。AtCoder Problems による Difficulty は 505 でした。
解答案
素朴に、クエリの回数 $Q$ 毎に、長さ $N$ の文字列の変換を行うと、計算量は、$O(NQ) = 2 \times 10^5 \times 2 \times 10^5 = 4 \times 10^{10}$ となり間に合いません。
変換テーブル m を用意します。初期値は、文字を変換しないテーブルとなります。
m[‘a’] = ‘a’, m[‘b’] = ‘b’, …, m[‘z’] = ‘z’
クエリで、c と d を読み込み、ある文字の変換先が c に一致した場合、d に書き換えます。変換テーブルを処理する計算量は、すべての文字について調べるため、$O(26 N) = 5.2 \times 10^6$ となり十分に間に合います。
C++ プログラム例（ABC342C）
変換テーブルは、map<char, char> を使います。クエリで変換テーブル m を更新して、後で、まとめて文字列を変換します。
以下が、C＋＋プログラムとなります。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin >> n;
string s;
cin >> s;
map<char, char> m;
for (int i = 0; i < 26; ++i) {
m[(char)(i + 'a')] = (char)(i + 'a');
}
int q;
cin >> q;
for (int i = 0; i < q; ++i) {
char c, d;
cin >> c >> d;
for (auto e : m) {
if (e.second == c) {
m[e.first] = d;
}
}
}
string result;
for (int i = 0; i < n; ++i) {
result += m[s[i]];
}
cout << result << endl;
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC342C）
Python 版も基本的な考え方は同じです。変換テーブルは辞書を使いました。string.ascii_lowercase で、”abc…xyz” が定義されています。以下となります。
"""AtCoder Beginner Contest 342 C"""
from string import ascii_lowercase
n = int(input())
s = input()
m = {}
for _, ch in enumerate(ascii_lowercase):
m[ch] = ch
q = int(input())
for i in range(q):
c, d = input().split()
for ch in m:
if m[ch] == c:
m[ch] = d
result = ""
for _, ch in enumerate(s):
result += m[ch]
print(result)こちらも「AC」と判定されました。
最後に
C問題からは、素朴なプログラムでは時間が間に合わない場合がでてきます。この問題は、変換テーブルだけを処理することがポイントでした。
引き続き ABC の問題を紹介していきます。
