Shirotsume の日記

嘘Greedyを生やすな

ABC196-F 「Substring 2」

道場鯖の練習セットにあった問題。事前にネタバレを食らっていたので、何を使うかは知っていたが考察は一からやった。このテクニックは非競プロでもよくつかわれるみたい。

atcoder.jp

問題概要

2 つの 01 文字列 S と T が与えられる。 T が S の連続部分文字列となるように S の文字を書き換えるときの最小回数を求めよ。

初めに: ハミング距離

同じ長さの 2 つの文字列が与えられた時、片方を書き換えてもう片方に一致させるために必要な書き換え回数の最小値のことをハミング距離という。

特に今回は、文字が 0, 1 なので、これをそのまま数として読んでしまうと、同じ長さの 2 つの文字列同士のハミング距離は以下のように表せる。

{\displaystyle \sum_{i=1}^N \left |S_i - T_i \right | }

特に、 01 列であることから、これは

{\displaystyle \sum_{i=1}^N \left (S_i - T_i \right )^{2} }

と等しく、式変形により

{\displaystyle  \sum_{i=1}^N \left (S_i - T_i \right )^{2}  = \sum_{i=1}^N S_i + \sum_{i=1}^N T_i  - 2 \times  \sum_{i=1}^N S_iT_i}

として計算できる。

元の問題の解法

さて、今回の問題では、 S' := S の k 文字目から N + k 文字目 とおいた時のハミング距離の最小値を求めればよいことになる。ナイーブにやると二乗かかってしまうので、式変形をうまく生かしたい。

{\displaystyle  \sum_{i=1}^N S'_i }

については容易に計算できるが、問題は

{\displaystyle  - 2 \times  \sum_{i=1}^N S'_iT_i}

である。これを書き直すと

{\displaystyle  - 2 \times  \sum_{i=1}^N S_{i + k}T_i}

ここで、 T を反転させてみる。そうすると、

{\displaystyle  - 2 \times  \sum_{i=1}^N S_{i + k}T_{N - i} = - 2 \times  \sum_{i + j = N + k} S_{i}T_{j}}

となり、FFT で計算できる形になる。

AC提出

atcoder.jp

実行時間がかなりギリギリ…