【ABC138】E - Strings of Impurity

atcoder.jp

解法

s’を文字の配列とみて、前からイテレータを動し、tと一致する文字を１文字ずつ探すことを考える。
最小値を求めたいので、一回一回のイテレータの移動は小さい方がよい。
この最小の移動を高速に求めるには、事前処理＋二分探索が有効になる。
事前に、sの中でそれぞれの文字がどの位置で登場するかを昇順で保持する配列を文字ごとに作成しておく。
現在のイテレータの位置をcurとすると、

• curより大きい位置でt[i]が登場している場合
  → curより大きい位置でt[i]が登場している場所へイテレータを動かし、動かした量を答えに加算する
• curより大きい位置でt[i]が登場していない場合
  → t[i]がsの中で初めて登場する位置へイテレータを動かし、元いた位置からsの最後までとsの最初から動かした位置までの変化量を答えに加算する

という感じで二分探索を活用して高速に答えを求めることができた。

ちなみに二分探索を使わない解法もある。

実装

英小文字は26文字しかないので、mapじゃなくてvectorでも良かった。
登場する文字の種類が少ないことに着目できる時もあるので覚えておこうと思う。

void solve(std::string s, std::string t){
    map<char, vector<int>> mp; // 文字の登場位置を格納
    map<char, int> mp_cnt; // 文字の登場回数
    int siz = s.size(), tsiz = t.size();
    REP (i, siz) {
        mp[s[i]].push_back(i);
        mp_cnt[s[i]]++;
    }

    ll ans = 0;
    int cur = -1; // 前回使用した文字の位置
    REP (i, tsiz) {
        // 二分探索して次にt[i]が登場する位置を特定
        auto iter = upper_bound(mp[t[i]].begin(), mp[t[i]].end(), cur);
        // cur以降にt[i]が登場しない場合は最初に戻る
        if (iter == mp[t[i]].end()) {
            // そもそもt[i]がsに含まれない場合
            if (!mp_cnt[t[i]]) {
                c(-1)
                return;
            }
            ans += siz - cur - 1; // 現在地から最後の間の文字数
            ans += mp[t[i]][0] + 1; // sの最初から初めてt[i]が登場するまでの文字数
            cur = mp[t[i]][0]; // sのなかで初めてt[i]が登場する位置
        } else {
            ans += *iter - cur;
            cur = *iter;
        }
    } 

    c(ans)
}