E - Strings of Impurity

問題

長いので、リンクを踏んでください
atcoder.jp

考察

・にない文字がに含まれる場合は明らかに-1
・部分列で構成しなければいけないので、単にに使う文字が出てくるまでを増やすのはダメ
・1時間ぐらい考えて二分探索が生える。ここから4時間ぐらい溶かす。

反省点

二分探索で得るべき値は、一つ前の文字より真に大きいindexを持つ.これは、をkeyとする配列で達成することができる。
間違ったアプローチのコードがこれ。
各文字ごとに最後に使ったindexを記録しておいて、その値を元に二分探索の範囲を限定する。
そもそも異なる文字のindexが最後に記録したindexより先に来る場合がある。間違ったアプローチは最小値にならない。

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define int ll
signed main(){
    string s; cin >> s;
    string t; cin >> t;
    vector<vector<int>> pos(26);
    for(int i = 0; i <  s.size(); ++i)
        pos[s[i] - 'a'].push_back(i);
    for(auto c : t)
        if(pos[c-'a'].empty())  return puts("-1") * 0;
    int ans = 0;
    int prevIndex = -1;
    int ssize = s.size();
    for(auto c : t){
        char key = c - 'a';
        auto itr = (upper_bound(pos[key].begin(),pos[key].end(),prevIndex));
        if(itr != pos[key].end()){
            ans +=  *itr - prevIndex;
        } else {
            itr = pos[key].begin();
            ans += ssize - prevIndex + *itr;
        }
        prevIndex = *itr;
    }
    cout << ans << endl;
}