AtCoder ABC 138の「E - Strings of Impurity」

はじめに

AtCoder Beginner Contest 138 の「E - Strings of Impurity」問題です。 解説では、ある文字→ある文字への距離を事前計算する方法と、二分探索で解く方法の両方が紹介されてましたが、自分は二分探索で解きました。

解き方

1. 結合後の文字は巨大なので、sとtの文字種が一致している限り、解がある
2. 文字ごとに出現位置を保持しておいて、都度二分探索で調べる

コード

typedef long long ll;

int main(int argc, char *argv[]) {
  string s,t;
  map<char, vector<int> > mp;
  cin>>s>>t;

  for(int i=0;i<s.size();i++){
    char c = s[i];
    mp[c].push_back(i);
  }

  for(int i=0;i<t.size();i++){
    char c = t[i];
    if(mp.count(c)==0){
      cout<<-1<<endl;
      return 0;
    }
  }

  ll res=0;
  int s_p=0;

  for(int i=0;i<t.size();i++){
    char c = t[i];
    auto it = lower_bound(mp[c].begin(), mp[c].end(), s_p);
    if(it == mp[c].end()){
      res += s.size() - s_p;
      s_p = 0;
      res += mp[c][0] - s_p + 1;
      s_p = mp[c][0] + 1;
    } else {
      res += *it - s_p + 1;
      s_p = *it + 1;
    }
  }

  cout<<res<<endl;

  return 0;
}

プログラミングコンテストチャレンジブック [第2版]　?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?