慶應SFC　環境情報学部　情報入試　2018年　大問Ⅴ　過去問解説

(ア)
A,Bの末尾が同じ文字である場合、末尾に対しては操作を行わなくていいからd(A’,B’)である。

何回か操作した後、最後の操作がaとbの置換である操作なら、d(A’,B’)+1であり、
最後の操作がbの挿入である操作ならd(A,B’)は決まっているのでd(A,B’)+1であり、
最後の操作がaの削除である操作ならd(A’,B)は決まっているのでd(A’,B)+1である。

そして、なるべく少ない操作の回数が編集距離であるから、上の3つの値の最小値がd(A,B)となる。

(イ)

実際のプログラミング経験があり、プログラミングのセオリーを知っていないと解けない高度な問題である。

まず、不等式が入ると分かる。
この段階ではiは登場していない。
ここはセオリーだが、i,jに対応するのはm,nである。
よって
j≦n
である。

次の段階でもjとnしか登場していない。
nに関係するのはBだから
j
である。

次の二つは、上と同じことをAに対して行い、処理Bを施すと分かる（これもセオリーである）。
よって
変数iの値を1にする（処理Aがi=0の場合なので、iは1から始める）
i≦mが成り立つ間、次の処理Bを繰り返す
である。

iの値が処理B中に変わっているので、にiを代入すると分かる。
jは処理Cで使っているので、1から始める。（j=0の場合は処理Aで求めてある）
Bの最後まで処理Cを行うので、j≦nが成り立つ間である。

あとは(ア)で考察したことを当てはめればよい。

が成り立つなら

であり、
成り立たないなら

の最小値とすればよい。