問題
文字列 $A$（長さ $N$）と $B$（長さ $M$）が与えられる。$A$ に対して「1 文字削除」「1 文字挿入」を繰り返して $B$ にするときの 最小操作回数 $D$ と、その操作列を出力せよ。置換は許さない（削除 + 挿入で 2 回と数える）。
操作列は次の形式で、編集グラフを左上から右下へ進む順に書く（後述の検査手順で $B$ が復元できれば正解。複数解がある場合はどれでもよい）:
- i: $A$ の $i$ 文字目（0-indexed）を削除する+ j: $B$ の $j$ 文字目（0-indexed）を挿入する
入力形式
A
B制約
| # | 条件 |
|---|---|
| 1 | $0 \le N, M \le 2 \times 10^5$、英小文字と英大文字のみ |
| 2 | $D \le 3000$ が保証される（差分が小さい前提。これが無いと本手法は $O(NM)$ に退化する——「迷った他案」参照） |
入出力例
入力例1
ABCABBA
CBABAC出力例1
5
- 0
- 1
+ 1
- 5
+ 5（A,B を削除 → C 一致 → B を挿入 → A,B 一致 → B を削除 → A 一致 → C を挿入。$N+M-2\cdot\mathrm{LCS}=7+6-2\cdot4=5$）
検査手順（ジャッジ）: $x=y=0$ から始め、各操作の前に $A[x]=B[y]$ である限り $x,y$ を同時に進める（対角線）。- i は $i=x$ を要求して $x$ を 1 進め、+ j は $j=y$ を要求して $B[j]$ を出力に加え $y$ を 1 進める。最後に対角線を進めて $x=N, y=M$ に着けば正解。
この問題は E. W. Myers「An O(ND) Difference Algorithm and Its Variations」（Algorithmica 1986、http://www.xmailserver.org/diff2.pdf 、2026-09-24 参照）の基本アルゴリズム（同論文 §3, Fig.2 の "greedy LCS/SES"）をそのまま問題化したものである。GNU diff・git の既定 diff（xdiff）はこの手法（と論文 §4b の線形空間版）に基づく。
概念図：編集グラフと最遠到達点
ヒント（クリックで段階的に開示）
ヒント1（方向性）
$A$ を横軸、$B$ を縦軸にとった $(N+1)\times(M+1)$ の 編集グラフ を考える。右へ 1 歩 = $A$ の 1 文字削除、下へ 1 歩 = $B$ の 1 文字挿入、$A[x]=B[y]$ のマスでは対角線（コスト 0）を進める。$(0,0)$ から $(N,M)$ への 対角線でない歩数の最小値 が $D$。LCS の DP はこのグラフ全体を埋めるが、$D$ が小さいなら 左上から右下への「対角線番号 $k=x-y$」の範囲は $[-D, D]$ しか使わない。
ヒント2（アプローチ）
$d=0,1,2,\dots$ の順に、「ちょうど $d$ 歩の非対角移動で、対角線 $k$ 上のどこまで（$x$ 座標の最大値）進めるか」を $V[k]$ に持つ。$d$ 歩で対角線 $k$ に来るには、$d-1$ 歩で $k-1$ に来て右へ、または $k+1$ に来て下へ、のどちらか。遠くまで進めている方を選ぶ（貪欲：同じ $(d,k)$ なら $x$ が大きいほど良い、という単純な優越関係が成り立つ）。到達後は対角線を滑れるだけ滑る（snake）。$(N,M)$ に届いた瞬間の $d$ が答え。
ヒント3（誘導）
V = [0] * (2*(N+M) + 2); off = N+M
for d in range(N+M+1):
for k in range(-d, d+1, 2): # d と k の偶奇は一致する
if k == -d or (k != d and V[off+k-1] < V[off+k+1]):
x = V[off+k+1] # 下へ（挿入）: k+1 から
else:
x = V[off+k-1] + 1 # 右へ（削除）: k-1 から
y = x - k
while x < N and y < M and A[x] == B[y]: x += 1; y += 1 # snake
V[off+k] = x
if x >= N and y >= M: return d
# 操作列の復元: 各 d の直前の V を保存しておき、(N,M) から逆にたどる模範解答 (Python)
模範解答を表示する（まず自力で解いてから）
import sys
def myers(a, b):
"""(D, script) を返す。script は ('-', i) / ('+', j) のリスト（編集グラフ順）。"""
n, m = len(a), len(b)
mx = n + m
off = mx
v = [0] * (2 * mx + 2)
trace = [] # d ごとの V のスナップショット（復元用）
D = None
for d in range(mx + 1):
trace.append(v[:])
for k in range(-d, d + 1, 2):
if k == -d or (k != d and v[off + k - 1] < v[off + k + 1]):
x = v[off + k + 1] # 下: B[y] を挿入
else:
x = v[off + k - 1] + 1 # 右: A[x] を削除
y = x - k
while x < n and y < m and a[x] == b[y]:
x += 1; y += 1 # snake（対角線）
v[off + k] = x
if x >= n and y >= m:
D = d
break
if D is not None:
break
# 復元: (n, m) から d を 1 つずつ戻す
x, y = n, m
script = []
for d in range(D, 0, -1):
vv = trace[d]
k = x - y
if k == -d or (k != d and vv[off + k - 1] < vv[off + k + 1]):
pk = k + 1
else:
pk = k - 1
px = vv[off + pk]; py = px - pk
while x > px and y > py: # snake を逆に戻る
x -= 1; y -= 1
if x == px:
script.append(('+', py)) # 下に来た = B[py] の挿入
else:
script.append(('-', px)) # 右に来た = A[px] の削除
x, y = px, py
script.reverse()
return D, script
def main():
lines = sys.stdin.read().split("\n")
a = lines[0].strip() if lines else ""
b = lines[1].strip() if len(lines) > 1 else ""
D, script = myers(a, b)
out = [str(D)] + [f"{op} {idx}" for op, idx in script]
sys.stdout.write("\n".join(out) + "\n")
main()計算量: 外側 $d$ は $D+1$ 回、内側は $d+1$ 個の対角線、snake の総移動は各 $d$ で $O(N+M)$ なので 時間 $O((N+M)D)$。上のコードは復元のために $V$ を $D$ 回コピーするので 空間 $O((N+M)D)$——これが本問で $D\le3000$ とした理由（$4\times10^5 \times 3000$ 整数は Python では重いが、実際に触るのは $[-d,d]$ の範囲のみ。真面目にやるなら各 $d$ で長さ $2d+1$ だけ保存して空間 $O(D^2)$ に落とせる）。
Step-by-Step 解説
右・下の移動のみを数えるので、経路の非対角歩数は $N+M-2\times(\text{対角線数})$。対角線数の最大値が LCS だから $D=N+M-2\,\mathrm{LCS}$。LCS の $O(NM)$ DP はこのグラフを全て埋めるが、Myers は「$d$ 歩で到達できる最遠点」だけを追跡する。
同じ対角線 $k$ 上で $d$ 歩の経路が 2 本あるとき、$x$ 座標が大きい方は小さい方の到達点から対角線を滑って到達できる点をすべて含む（Myers 論文 Lemma 2 の「furthest reaching D-path」）。したがって各 $(d,k)$ について $x$ の最大値だけ覚えればよく、状態数は $O(D^2)$ 個。
$k=x-y$ は右移動で $+1$、下移動で $-1$ 変わるので $d$ 歩後の $k$ は $d$ と同じ偶奇。よって内側ループは range(-d, d+1, 2)。V[off+k±1] は前回の $d-1$ の値（偶奇が違うので今回の更新と衝突しない）——1 本の配列を上書きしてよい理由がこれ。
k == -d or (k != d and V[k-1] < V[k+1]) は「左端なら必ず下から」「右端なら必ず右から」「それ以外は遠い方から（同点なら右＝削除優先）」。同点で削除を先にするのは論文の慣習で、diff の出力が「消してから足す」の順になる。逆にしても $D$ は変わらない。
$d$ ごとの $V$ を残し、$(N,M)$ から「今の $k$ はどちらから来たか」を同じ判定式で再現して前の $d$ の点へ戻る。snake の長さは while x > px and y > py で吸収する。入力例1 では $(7,6)\to(6,5)$（$D=5$ の snake）→ 挿入 + 5 → … と戻り、反転して出力例の順になる。
git の xdiff は本論文 §4b の 線形空間版（前からと後ろからの探索を中央で出会わせる分割統治、Hirschberg Day141 Q1 と同型）を使い、さらに「コストが大きくなりすぎたら途中で打ち切って近似する」ヒューリスティック（XDL_HEUR_MIN_COST）を持つ。本問の基本形は trace に $V$ を全て残すので空間が $O((N+M)D)$ になっており、そのままでは巨大ファイルに使えない。
迷った他案と採らなかった理由
| 案 | 計算量 | 採否 | 理由 |
|---|---|---|---|
| LCS の $O(NM)$ DP（1 行ずつ） | 時間 $O(NM)$、空間 $O(M)$ | 比較用 | $N=M=3000$ で 0.59 s（実測）。$N=M=2\times10^5$ では $4\times10^{10}$ で不可能。$D$ の大小に無関係に遅い |
| ビット並列 LCS（Day158 Q4） | $O(NM/w)$ | 不採用 | $N=M=5\times10^4$ で 0.33 s と速いが、$2\times10^5$ では $4\times10^{10}/64\approx6\times10^8$ 語演算でまだ重い。$D$ が小さいことを活かせない |
| Myers 基本形（本解） | $O((N+M)D)$ | 採用 | $D=34$ なら $N=M=2\times10^5$ で 0.013 s（実測）。「差分は小さい」という diff の実態に計算量が比例する |
| Myers 線形空間版（middle snake 分割統治） | 時間 $O((N+M)D)$、空間 $O(N+M)$ | 扱わない | git が使う実戦形。本問は $D\le3000$ で基本形の空間で足りるので範囲外にした。前提が「$D$ が $10^5$ 級でもよい」に変わったらこちら |
| Wu–Manber–Myers–Miller $O(NP)$（$P$=削除数） | $O(N P)$ | 扱わない | $N\ll M$ で挿入が多い非対称な差分ではさらに速い（$P\le D/2$）。同じ論文系統の派生 |
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
k を range(-d, d+1) で回す | 偶奇の制約を忘れる | range(-d, d+1, 2)。奇数ずれの $V$ は前回の値で、上書きすると壊れる |
| 配列の添字が負になる | $k\in[-D,D]$ | オフセット off = N+M を足す |
| snake の前に終了判定する | 対角線を滑った後で $(N,M)$ に届く | while の後に if x >= n and y >= m |
| 復元時に snake を戻し忘れる | $(x,y)$ が前の点 $(px,py)$ と一致しない | while x > px and y > py: x -= 1; y -= 1 を先に行う |
| 空文字列で落ちる | $N+M=0$ のとき配列長 2、ループ 1 回で終了するはず | mx == 0 なら D=0 を即返す（本解は range(1) で $d=0$ を処理し、$x\ge0, y\ge0$ で終了するので落ちない） |
次のステップ
- 発展1: 線形空間版を実装する——前向き探索と後ろ向き探索を同時に進め、両者が重なった対角線（middle snake）で分割し再帰する（論文 §4b、Hirschberg Day141 Q1 と同じ発想）
- 発展2: 行単位の diff にする——各行をハッシュして整数列に変換すれば同じコードで動く（GNU diff / git はこの形）。「共通の接頭辞・接尾辞を先に剥がす」前処理で実用上さらに速くなる
- 扱わなかった範囲: 置換を 1 操作と数える Levenshtein 距離（Ukkonen 1985 の $O(ND)$ 帯 DP・Day133 Q4 のオートマトン）、「見た目が良い diff」のための後処理（git の
--patience/--histogram、indent heuristic）
検証ログ（本セッションで実行した数値）
- 入力例1（論文の例
ABCABBA/CBABAC）: $D=5$、操作列[('-',0),('-',1),('+',1),('-',5),('+',5)]。kitten/sitting: $D=5$（LCS=4 から $6+7-8=5$ と一致） - ランダム 3000 件（$N,M\le12$、アルファベット 2〜4 種）: $D$ を LCS DP から求めた $N+M-2\,\mathrm{LCS}$ と比較 → 不一致 0 件。操作列は上記「検査手順」で $B$ を復元 → 不正 0 件、長さは全件 $D$ に一致
- 性能（実測、$N=M=3000$）: 編集 5 箇所（$D=5$）で Myers 0.000 s / DP 0.593 s。編集 50（$D=70$）で 0.001 s / 0.606 s。編集 500（$D=651$）で 0.052 s / 0.603 s
- 性能（実測、$N=M=2\times10^5$、置換 20 箇所 → $D=34$）: 0.013 s
- 最悪ケース（実測、
a×2000 vsb×2000、$D=4000$）: 1.763 s——$O((N+M)D)=O(NM)$ に退化する例。制約に $D\le3000$ を置いた根拠 - 出所ラベル: すべて実測（Python 3.14）。git の
xdiffの内部構造は原論文と git ソース（xdiff/xdiffi.c）に基づく記述で、本セッションでは実行していない - 検証スクリプト: スクラッチパッドの
q2.py