慶應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が成り立つ間である。

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

が成り立つなら

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

の最小値とすればよい。

AO入試・小論文に関するご相談・10日間無料添削はこちらから

「AO入試、どうしたらいいか分からない……」「小論文、添削してくれる人がいない……」という方は、こちらからご相談ください。
(毎日学習会の代表林が相談対応させていただきます!)









コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です