😇

ABC324-C : Error Correction の珍回答供養 (Julia言語)

2023/11/04に公開

Julia

競技プログラミング

tech

経緯(当時の思考過程)

久しぶりに競プロの問題でも解くかなと思って上の問題を開いた。
いやこれめちゃくちゃ難しいぞ。。。

とりあえず編集距離(レーベンシュタイン距離)くらいは知っていたので問題は「 $S$ と $T$ の編集距離が1以下かどうか $N$ 回判定せよ」という問題であることくらいはわかった。

普通に編集距離を計算すればよいのでは？： $O(N^2)$ かかるから無理そう
$T$ から編集距離1以内の文字列を全て列挙しておけばよいのでは？：筋が良さそうと思ったが定数倍(アルファベットの数とか)がきつそう

頭を抱えていたとき、謎の天啓が降りて来たのであった・・・

珍回答の解説

「ある文字列 $S$ と $T$ の編集距離が1以下であることを判定するためには二分探索を行えばよい」ということを思いついてしまった。以下にその解説を行う。

まず、一般に $|S| \ge |T|$ として一般性を失わない。
命題 $P(t)$ 「 $T$ の1文字目から $t$ 文字目までは $S$ の1文字目から $t$ 文字目までと完全に一致している」を考えてこれを満たす最大の $t$ を求めたい。

t^* := \max{\{t|P(t)\,\,\mathrm{is}\,\,\mathrm{true} \}}

$P(t)$ は $t$ に関して単調(あるところまでは全て真でそこ以降は全て偽)であるため二分探索を用いれば $O(\log{|T|})$ で解ける。

解いた後、「文字列 $S$ と $T$ は $t^*$ 文字目までは完全に一致していて $t^*+1$ 文字目は異なる」ということがわかる。ということは $S$ の $t^*+1$ 文字目と $T$ の $t^*+1$ 文字目のいずれかあるいは両方を編集する必要がある。

ここで $|S| \ge |T|$ と仮定したことと、編集距離が1以下であるかを判定することに注意すれば「 $S$ の $t^*+1$ 文字目に挿入」と「 $T$ の $t^*+1$ 文字目を削除」の操作は禁止されていることがわかる。したがって許される操作は

$S$ の $t^*+1$ 文字目を削除
$T$ の $t^*+1$ 文字目に $S$ の $t^*+1$ 文字目を挿入
$S$ の $t^*+1$ 文字目を $T$ の $t^*+1$ 文字目に置換
$T$ の $t^*+1$ 文字目を $S$ の $t^*+1$ 文字目に置換

の計4種である。ただし実際には「 $S$ の $t^*+1$ 文字目を $T$ の $t^*+1$ 文字目に置換」と「 $T$ の $t^*+1$ 文字目を $S$ の $t^*+1$ 文字目に置換」は本質的に同じであり、「 $T$ の $t^*+1$ 文字目に $S$ の $t^*+1$ 文字目を挿入」すれば実質 $t^*+1$ 文字目は無視できるため「 $S$ の $t^*+1$ 文字目を削除」したことと等価な操作であるため可能な操作は2種類となる。この2種類の操作に対して以下のような解釈が可能。

$S$ の $t^*+1$ 文字目を削除
- $S$ の $t^*+2$ 文字目から最後までの部分文字列と $T$ の $t^*+1$ 文字目から最後までの部分文字列を比較する
$S$ の $t^*+1$ 文字目を $T$ の $t^*+1$ 文字目に置換
- $S$ の $t^*+2$ 文字目から最後までの部分文字列と $T$ の $t^*+2$ 文字目から最後までの部分文字列を比較する

しかも、 $|S| = |T|$ の時は挿入、削除を行えば編集距離が1にならないため禁止される(つまり置換のみが可能である)し、逆に $|S| > |T|$ の場合は少なくとも必ず挿入、削除を行わなければならない。
ここから、「 $S$ の $t^*+2$ 文字目から最後までの部分文字列」と「 $T$ の $t^*+1+\mathbb{1}_{|S|=|T|}(|T|)$ 文字目から最後までの部分文字列」比較して、同一であれば編集距離は1以内で、そうでなければ2以上かかるということがわかる。ただし $\mathbb{1}_{|S|=|T|}(|T|)$ は以下に定義される指示関数である。

\mathbb{1}_{|S|=|T|}(|T|) = \begin{cases} 1 & \mathrm{if}\,\,|S|=|T| \\ 0 & \mathrm{otherwise} \end{cases}

このクエリを $N$ 回行えばよいので結局最悪計算量 $O(N\log{N})$ くらいで計算できそう！

コード供養😇

bs(ok, ng, S, T) = (m=(ok+ng)÷2; return ng-ok≡1 ? ok : (S[1:m]==T[1:m] ? bs(m, ng, S, T) : bs(ok, m, S, T)))
function main()
    _, t = split(readline())
    a, l = [], length(t)
    for (n, s) in enumerate(readlines())
        D = length(s) - l
        (S, T) = D ≥ 0 ? (s, t) : (t, s)
        m = bs(0, length(T) + 1, S, T)
        S[m+2:end]==T[m+1+!(abs(D)>0):end] && push!(a, n)
    end
    println(length(a), '\n', join(a, " "))
end
main()

なぜ珍回答なのか

公式の解説を見るとなんとSを1回だけミスマッチを許して1から走査していた。
何！？それでは計算量 $O(N^2)$ でTLEするのではないのか！？
ここで問題の制約条件を見てみましょう

ん・・・？

🤔🤔🤔🤔🤔🤔🤔🤔

ということで解説の計算量はざっくり言って $O(|S_1|+|S_2|+...+|S_N|) = O(10^5)$ 程度で動作しそうですね。めでたしめでたし😇

二分探索の方も実は計算量の見積もりは間違っていて、

O(\log{|S_1|}+\log{|S_2|}+...+\log{|S_N|})=O\left(\log{\prod_{i=1}^N|S_i|}\right)

くらいだったようですね。
二分探索の解法は制約条件を全く見ていないことによる奇跡の(？)解法だったのでした。

余談

l = length(t)をfor文の中で計算させるとTLEになってしまう。。。
文字列の長さの計算ってそんなに重い計算なんですかね？情報求ム

まとめ

日本語が読めてないせいで謎の回答にたどり着いてしまった。
制約条件には気を付けよう！
でも一生懸命考えた時間はプライスレス！(現実逃避)

Reference

とても良いめぐる式二分探索の解説記事です。おすすめ。