みんなのプロコン2017本選-A YahooYahooYahoo
概要
最大10万長の文字列Sが与えられる。"yahoo"を0以上の任意の整数回繰り返した文字列とSの編集距離の最短を答えよ。
ACするまで
1. 超有名問題、レーベンシュタイン距離だ！
2. 愚直にやると、yahooを繰り返したものの長さが最大10万になりうるので、O(MN)の愚直な動的計画法では間に合わない。
3. 繰り返してるのはyahooの五文字、もしかしたらこの五文字のどれを見てることだけメモすればいけのではないか？
4. DPテーブルの定義を少し変えてみて、計算するときは"yaho"から"(yahoo)"になることを考慮してループするようにする。
5. ただ普通にループさせると、"yahoo"のようなものはいいが("yaho" -> "yahoo")、空文字列もループしてしまう(空文字列は先ほどの例のように一文字減らせない)。対策としては、同じ計算を2回すればよい
6. AC
考察
普通の編集距離のコードはこれである。
judge.u-aizu.ac.jp
これから手直しをしていく。
まず、対象文字列が
- "yahoo" * (0以上の整数) + "" -0番
- "yahoo" * (0以上の整数) + "y" -1番
- "yahoo" * (0以上の整数) + "ya" -2番
- "yahoo" * (0以上の整数) + "yah" -3番
- "yahoo" * (0以上の整数) + "yaho" -4番
の5種類に分けられる。
そして、dp[i][j] := Sのi文字目とyahoo文字列のj番目
と定義すればうまくいく！(そういうものと考えたほうがよさそう)
この時遷移を考える。
まずは次の二つの遷移だが、これは普通の編集距離と同じである。ただし、ループをするので下記のような書き方をすること。
ちなみに、初期化の際にはdp[0][0]は0、それ以外はすべてINFで初期化する。
int tmp = INF; tmp = min(tmp, dp[i - 1][j] + 1); tmp = min(tmp, dp[i - 1][(j + 4) % 5] + 1);
編集距離で二つの文字が一致してる時のパターンでは、これもTのインデックスを少し変更してる以外同じ(T[j] := j-1文字目から、j文字目に定義しなおした)
//これが普通の編集距離 tmp =min(tmp, dp[i - 1][j - 1] + (S[i - 1] == T[j - 1] ? 0 : 1)); //これがローリングする今回の問題の更新 tmp = min(tmp, dp[i - 1][(j + 4) % 5] + (S[i - 1] == T[j] ? 0 : 1));
まとめて書くとこうなる。
for (int j = 0; j < T.size(); j++) { int tmp = 1145141919; if (i > 0)tmp = min(tmp, dp[i - 1][j] + 1); tmp = min(tmp, dp[i][(j + 4) % 5] + 1); if (i > 0) { int c = 0; if (S[i - 1] != T[(j + 4) % 5])c = 1; tmp = min(tmp, dp[i - 1][(j + 4) % 5] + c); } dp[i][j] = tmp; }
そして、これをループ内に1つだけ書くと、次のようなケースで落ちる。
"yah”と("yahoo")*n個+""の編集距離は、本来ならば"yahoo"との距離2が正しいはずなのに、上記の計算では""との距離3とみなされる。
理由としては、正しい答えでは、dp[5][0]の時点でdp[5][4]を参照してる(ループしてるので)が、この時dp[5][4]はまだ計算されてないからである。
計算結果の参照がループするので、2回上の計算をしなければ完璧に最善の結果が伝播しない。
逆に、2週以上をまたぐ方法は最善ではない(必ず1週またぐもしくはまたがない方法で置き換え可能)ので、ループは2回でよい。
一言
このようなループさせる手法は有向ベルマンフォードでグラフに少なくとも1つの閉路があるかを検出する際に、辺の数の2倍回すことと共通してる(無向グラフならば辺の数だけ回せばよい。値の伝達は無向なので1回で済む。一方有向グラフでは自分自身に戻ってくるまでに最低辺の数だけかかるため)。
