Learning Algorithms

アルゴリズムの勉強メモ

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