みんなのプロコン 2017 本選 A YahooYahooYahoo
問題概要
文字列 が与えられるので、 'yahoo'の繰り返しの文字列にするための編集距離を求めよ。
制約
解法
dp[ ][ ] := ] を「 'yahoo' の繰り返し + 'yahoo' の先頭 文字」の文字列にするための編集距離
としてDPする。
dp[0][0]は0、その他はINFで初期化する。
遷移は、dp[ ][ ] ( ] と 'yahoo' の 文字目)を見ているとき
- 削除 … 編集距離は1増えて、次は ] と 'yahoo' の 文字目を見る
- 挿入 … 編集距離は1増えて、次は ] と 'yahoo' の 文字目を見る
- 変更 … ] が 'yahoo' の 文字目と同じならば編集距離は変化せず、異なるならば編集距離は1増える。次は ] と 'yahoo' の 文字目を見る
となる(普通の編集距離のDPとほぼ同じ)。
注意が必要なのは挿入の遷移で、更新式が
dp[ ][1] = min(dp[ ][1], dp[ ][0]+1);
dp[ ][2] = min(dp[ ][2], dp[ ][1]+1);
dp[ ][3] = min(dp[ ][3], dp[ ][2]+1);
dp[ ][4] = min(dp[ ][4], dp[ ][3]+1);
dp[ ][0] = min(dp[ ][0], dp[ ][4]+1);
dp[ ][1] = min(dp[ ][1], dp[ ][0]+1);
…
と循環してしまうため、 は0から4までを1周するだけでは足りない。(2周すれば大丈夫らしいけどたくさん回しました)