Substring 2 [AtCoder Beginner Contest 196 F]

https://atcoder.jp/contests/abc196/tasks/abc196_f

解説

https://atcoder.jp/contests/abc196/submissions/21122079 えー、どれだけ考えても分からなかったのですが、FFTを使うということで、なるほどという感じでした。

公式解説

AtCoderの解説から解説動画を見ると、すべて理解できるが、重ねて解説する。
S = 101
T = 100
この2つについて異なっている項目数を高速に数えるには、Tを逆転させる。
S = 101
T'= 001
この状態のままFFTをして、配列cを得たとする。
すると、c[2] = S[0]T'[2] + S[1]T'[1] + S[2]*T'[0]となり、今回はc[2]=1となる。
これはどういうことかというと、どちらも1の場合に積を取ったら1となって、どちらも1の場合が抜き出せている。
FFTで位置を対応させるためにTを反転させていて、このままだとどちらも1の場合の組み合わせが抽出可能

これを今回の問題に発展させると、0と1, 1と0の組み合わせが得られればいいので、
どちらもTを反転させたあと、0と1なら、Sの0を1にして、Tの1を1のままにしてFFTすると、0と1のペアが得られる。
1と0も同様に行って、個数を足し合わせれば、異なっている個数が得られて、それが書き換え必要な回数となる。
よって、これの最小値を取ればいい。

他の解法1

2つ分解して解いたが、1と-1をうまく使って1回のFFTで解く方法もある。
モチベーションは同じだが、同じだったら-1, 違っていたら1みたいな感じにして、
最後に+Tの長さをすると、違っている部分の個数×2になるみたいなのをうまく使う。
賢い。

他の解法2

bitset高速化で解く。
よぎったが、10¹²の高速化なので、さすがに難しそうと思ったが、やりようによっては通るみたい。
追加テストケースがあったみたいで、現状でも通るかは分からない。

https://twitter.com/_su1sen/status/1373278366913028103

上記ツイートのようにアラインメントを調整することで高速化してACまで持ち込んでいる。
これは賢いな…初見のテクだ…

string S, T;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> S >> T;
    reverse(all(T));

    int NS = S.length();
    int NT = T.length();

    vector<ll> a01(NS);
    rep(i, 0, NS) a01[i] = (S[i] == '0' ? 1 : 0);

    vector<ll> b01(NT);
    rep(i, 0, NT) b01[i] = (T[i] == '0' ? 0 : 1);

    auto c01 = convolution(b01, a01);

    vector<ll> a10(NS);
    rep(i, 0, NS) a10[i] = (S[i] == '0' ? 0 : 1);

    vector<ll> b10(NT);
    rep(i, 0, NT) b10[i] = (T[i] == '0' ? 1 : 0);

    auto c10 = convolution(b10, a10);

    ll ans = inf;
    rep(i, NT - 1, NS) chmin(ans, c01[i] + c10[i]);
    cout << ans << endl;

}