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

問題概要

与えられる文字列sと'yahoo'の0回以上の繰り返しの文字列との編集距離を求める．

解法

普通の編集距離DPを元にいくつかアレンジを加える．

• 編集先文字列はインデックスjについてj%5が0,1,2,3,4番目の文字がそれぞれy,a,h,o,oの文字列と考える
• 'yahoo'に関するループは2回回す(ソースコード中のrepp(j, 10)にあたる．ループが1回でいいならrepp(j,5)になるはず)

この問題ではdp[i][4] -> dp[i][3] -> dp[i][2] -> dp[i][1] -> dp[i][0] -> dp[i][4] -> …のように，dpの更新時に使う値が循環しうる． ループを2回回さないと，例えば'yahooahoo'のような文字列でWAが出てしまう．

ソースコード

#include<iostream>
#include<string>

#define rep(n) for(int i=0;i<n;i++)
#define repp(j, n) for(int j=0;j<n;j++)
 
using namespace std;

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    string s;
    cin >> s;
    int n = (int)s.length();
    int dp[n+1][5];
    fill(dp[0], dp[n+1], 1000000);

    rep(n) dp[i+1][0] = i+1;
    rep(5) dp[0][i] = i;
    rep(n){
        repp(j, 10){
            if(
                (j%5 == 0 && s[i] == 'y')
                || (j%5 == 1 && s[i] == 'a')
                || (j%5 == 2 && s[i] == 'h')
                || (j%5 >= 3 && s[i] == 'o')
            ){
                dp[i+1][(j+1)%5] = min(dp[i+1][(j+1)%5], dp[i][j%5]);
            }else{
                dp[i+1][(j+1)%5] = min(dp[i+1][(j+1)%5], dp[i][j%5]+1);
            }
            dp[i+1][(j+1)%5] = min(dp[i+1][(j+1)%5], dp[i+1][j%5]+1);
            dp[i+1][(j+1)%5] = min(dp[i+1][(j+1)%5], dp[i][(j+1)%5]+1);
        }
        
    }

    cout << dp[n][0] << endl;
    return 0;
}

感想

AtCoderの400点問題全部埋まって嬉しい．残ってる500点問題はどれも重そうだな……．

自分の研究に関連する論文でも編集距離出てきたし，NLPの教科書でも編集距離ってよく出てくるのに，そういえば実装したことなかったなぁ．