AtCoder ABC 342 C - Many Replacement (3Q, 茶色, 350 点)

これ実は「アルファベット文字の変換テーブルを愚直に作る」という素朴な方法が解けるけど、意外と盲点になりそうだ！

• 問題へのリンク

問題概要

英小文字のみからなる長さ の文字列 が与えられる。次の 回の操作を実行後の文字列を出力せよ。

【操作】
文字 が与えられるので、文字列 中の文字 をすべて文字 に置き換える

制約

• 

考えたこと

これ一瞬、高度なデータ構造が必要に思えるのだけど、注目すべきことはたった 1 つ。

---

英小文字は 26 種類しかない

---

というところだ。文字列 の長さがたとえ などあったとしても、同じ文字に対する最終結果は同じなのだから、高々 26 箇所だけ考えれば良いのだ！！！

具体的には、次のような配列を求めよう。

---

• convert[c]：文字 が操作によってどの文字に変わるか

---

そして、 回のクエリでこの値を順次更新していく。具体的には、クエリ に対しては

• convert[x] == c であるようなすべての に対して
• convert[x] = d と更新する

というようにすればよい。

計算量は、英小文字の種類数を として、 と評価できる。

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N, Q;
    char c, d;
    string S;
    cin >> N >> S >> Q;

    vector<int> convert(26);
    for (int i = 0; i < 26; i++) convert[i] = i;
    while (Q--) {
        cin >> c >> d;
        c -= 'a', d -= 'a';

        // 文字 c を文字 d に書き換える
        for (int i = 0; i < 26; i++) {
            if (convert[i] == c) convert[i] = d;
        }
    }

    // もとの文字列を書き換える
    for (auto &c : S) c = (char)(convert[c - 'a'] + 'a');
    cout << S << endl;
}