ABC 386 F — Operate K

考察

通常の編集距離DPは|S||T|だが、dp[i][j]≥|i-j|である。判定閾値K≤20を超える|i-j|のcellは最終的なYes経路へ参加できない。挿入・削除・置換の各遷移は距離を減らさないので、対角線から幅Kのbandだけ正確に計算すれば判定結果を保てる。長さ差がKを超えるなら編集距離も必ずK超なので即Noにできる。band外をINF=K+1として扱えば、境界から誤って安い遷移が入ることを防げる。

採用する候補: Levenshtein DPを|i-j|≤Kの帯状領域だけで計算する

各rowの有効cellがO(K)個になり、標準遷移をそのままO((|S|+|T|)K)へ削減できる。

棄却する候補: 全(|S|+1)(|T|+1) cellの編集距離DP

文字列長が5×10^5で二次時間・メモリとも不可能である。

長さ差がKを超えるなら編集距離も必ずK超なので即Noにできる。

まず長さ差を判定する。rolling arrayでiを進め、jを[max(0,i-K),min(|T|,i+K)]だけ走査し、削除・挿入・一致/置換の標準三遷移をK+1でcapする。最後がK以下か答える。

典型の発動条件

banded edit-distance DP

発動条件: 編集距離が小さいかだけを、小さい閾値Kで判定するとき。

下界|i-j|で不要cellを除き対角帯だけ計算する。

閾値DPのcap

発動条件: K以下かだけが必要で値が単調非減少するとき。

K+1以上を同じINFへ丸めて状態を安全に制限する。

問題固有の要素

入力長は巨大でもYesとなり得るalignmentは主対角からK以上ずれられず、制約KがDPの幾何的な幅を決める。

別の問題へ持ち帰る視点: 二次元DPで目的値に簡単な下界があるなら、閾値判定では下界が閾値を超える領域を切り落とす。

正当性

prefix長差|i−j|は挿入削除の最低回数なのでKを超えるcellは最終距離K以内pathに現れない。帯内の標準三遷移は全許容編集列を網羅する。K+1でcapしても≤K判定は変わらない。

実装上の注意

  • rowごとにj範囲がずれるためrolling index対応を明示し、空prefixの初期値をband内だけ設定する。|S|-|T|の絶対値を先に確認する。

復習の核

  • 空prefix境界、長さ差がKちょうど/K+1、全一致、挿入と削除が交互に必要な短列をfull DPとrandom比較する。

計算量と制約

時間

文字列長n,m、許容編集K。帯内 O((n+m)(K+1))。

空間

rolling band O(K+1)、入力O(n+m)。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: Each of S and T is a string of length between 1 and 500000, inclusive, consisting of lowercase English letters.; K is an integer satisfying \color{red}{1 \le K \le 20}.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Operate K の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 列・subsequence DP

主題
  • 列・subsequence DP: 二つの列prefixを状態にし、一致・挿入・削除・置換の編集費用を最小化できる。閾値Kの判定では長さ差の下界から|i-j|≤Kの対角帯だけを計算できる。
追加で学ぶ技能
    なし
    既習技能

    主タグ: 編集距離・sequence alignment DP

    補助タグ: DPの最小十分状態

    執筆: abc-explanation-author1.1.1 / revision 2

    学習の位置

    体系上の位置: 列・subsequence DP

    • 二つの列prefixを状態にし、一致・挿入・削除・置換の編集費用を最小化できる。閾値Kの判定では長さ差の下界から|i-j|≤Kの対角帯だけを計算できる。

    先に読む単元:

    学習記録

    状況更新: 更新記録なし

    復習設定更新: 更新記録なし

    端末内の保存状態を確認しています。

    要復習一覧 / 学習記録のバックアップ / 解説に戻る

    同じ単元の問題