Atcoder Grand Contest 007 F. Shik and Copying String
Atcoder Grand Contest 007 F. Shik and Copying String
F: Shik and Copying String - AtCoder Grand Contest 007 | AtCoder
感想
考えることはシンプルなんだけど条件が難しい
解法
$\ T\ $の連続する文字の先頭文字と、それに対応する$\ S\ $の文字を決定できる。これがうまく対応させられないときは構成不可能で、逆に対応させることができれば構成可能である。
これらを$\ s + 1\ $回以下の操作で構成できるための条件は、$\ S\ $と$\ T\ $の対応する位置を$\ a\ $と$\ b\ $で表すと、任意の$\ i\ $について、$\ a_{i + s} - s \geq b_i\ $が成り立つことである。よってこれは二分探索で求めることができる。この条件は、絵を書いて$\ 1\ $時間くらいにらめば思いつく(ほんまか?)。
実装
#include "bits/stdc++.h" using namespace std; int main() { int n; scanf("%d", &n); string s, t; cin >> s >> t; if (s == t) return !puts("0"); if (s[0] != t[0]) return !puts("-1"); vector<int> a, b; b.push_back(0); for (int i = 1; i < n; i ++) if (t[i] != t[i - 1]) b.push_back(i); int k = b.size(); int p = n - 1; int bp = k - 1; while (p > 0) { while (t[b[bp]] != s[p]) p --; if (p == 0) break; a.push_back(p); bp --; p = min(p, b[bp]); } a.push_back(0); reverse(a.begin(), a.end()); if (a.size() != k) return !puts("-1"); int lb = -1, ub = k; while (ub - lb > 1) { int s = (lb + ub) / 2; bool ok = true; for (int i = 0; i < k; i ++) { if (i + s < k) ok &= a[i + s] - s >= b[i]; } if (ok) ub = s; else lb = s; } printf("%d\n", ub + 1); return 0; }