【AtCoder】ABC 342 C - Many Replacement | 茶コーダーが解くAtCoder

atcoder.jp

実行時間制限: 2 sec / メモリ制限: 1024 MB / Difficulty: 505

問題概要

英小文字からなる長さ の文字列 が与えられる。 に対して以下の操作を 回行うので、全ての操作が終わった後の を出力せよ。

• 回目の操作 : に含まれる文字 を全て文字 に置き換える。

制約

• 
• は整数
• は英小文字

考察

問題文の指示の通りに実装しようとすると、 C++ のreplace関数を用いて 回の操作をシュミレーションすることになる。しかし、例によって であり、このシュミレーションの計算量は なので間に合わない。

そこで、計算量を落とせないか考えてみよう。改善点としてまず思いつくのは、 回の操作をいちいちシュミレーションする必要があるのか、という点だ。どうにかして 回の操作を1回で処理したいところだ。

ここで、 自体に操作をするのではなく、置き換える文字とその置き換え先の文字の関係を更新することを考える。これは、サンプルケース1において、rをaと置き換えた後、再度aをrで置き換えていることがヒントである。rは最終的にrのまま変わらないので、途中でaに変換する必要はないのである。

置き換える文字とその置き換え先の文字の関係は、前者をkey、後者をvalueとするmapで管理するとよいだろう。具体的なアルゴリズムは以下のようになる。

• mapをmap['a'] = 'a', map['b'] = 'b', ..., map['z'] = 'z'で初期化する。
• 入力 を受け取り、value = c_iとなるkeyのvalueをd_iとする。
• の各文字を先頭から順番に見ていき、 文字目についてmap[S[i]]を出力用の文字列の 文字目とする。

あとはこれを実装していくだけ。map[c] = dとしないように注意 (1敗) 。

コード

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

#define rep(i, start, end) for (ll i = (start); i < (ll)(end); i++)

// ======================================== //

int main()
{
    int N, Q;
    string S;
    cin >> N >> S >> Q;
    map<char, char> mp;
    rep(c, 'a', 'z' + 1) mp[c] = c;
    rep(i, 0, Q)
    {
        char c, d;
        cin >> c >> d;

        for (auto &&m : mp)
        {
            if (m.second == c)
                mp[m.first] = d;
        }
    }

    string ans = "";
    rep(i, 0, S.size())
    {
        ans += mp[S[i]];
    }

    cout << ans << endl;
}

atcoder.jp

実装時間: 20分