足跡-sokuseki-

りかの日進月歩の記録

みんなのプロコン 2017 本選 A YahooYahooYahoo

A - YahooYahooYahoo

問題概要

文字列  S が与えられるので、 'yahoo'の繰り返しの文字列にするための編集距離を求めよ。

制約
 1 \le |S| \le 10^5

解法

dp[  i ][  j ] :=  S[0…i ] を「 'yahoo' の繰り返し + 'yahoo' の先頭  j 文字」の文字列にするための編集距離

としてDPする。

dp[0][0]は0、その他はINFで初期化する。

遷移は、dp[  i ][  j ] (  S[i ] と 'yahoo' の  j 文字目)を見ているとき

  • 削除 … 編集距離は1増えて、次は  S[ i+1 ] と 'yahoo' の  j 文字目を見る
  • 挿入 … 編集距離は1増えて、次は  S[i ] と 'yahoo' の  j+1 文字目を見る
  • 変更 …  S[ i ] が 'yahoo' の  j 文字目と同じならば編集距離は変化せず、異なるならば編集距離は1増える。次は  S[i+1 ] と 'yahoo' の  j+1 文字目を見る

となる(普通の編集距離のDPとほぼ同じ)。

注意が必要なのは挿入の遷移で、更新式が
dp[  i ][1] = min(dp[  i ][1], dp[  i ][0]+1);
dp[  i ][2] = min(dp[  i ][2], dp[  i ][1]+1);
dp[  i ][3] = min(dp[  i ][3], dp[  i ][2]+1);
dp[  i ][4] = min(dp[  i ][4], dp[  i ][3]+1);
dp[  i ][0] = min(dp[  i ][0], dp[  i ][4]+1);
dp[  i ][1] = min(dp[  i ][1], dp[  i ][0]+1);

と循環してしまうため、 j は0から4までを1周するだけでは足りない。(2周すれば大丈夫らしいけどたくさん回しました)


Submission #2164134 - 「みんなのプロコン」本選 オープンコンテスト