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高速化で解く。
よぎったが、1012の高速化なので、さすがに難しそうと思ったが、やりようによっては通るみたい。
追加テストケースがあったみたいで、現状でも通るかは分からない。
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; }