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; }