A - YahooYahooYahoo 「みんなのプロコン」本選 オープンコンテスト 2017

A - YahooYahooYahoo

問題概略
文字列Sのyahoo....yahooへのレーヴェンシュタイン距離を求めよ。

制約
10^5

解法
[i]までをy,a,h,o,oにする場合で遷移していく（レーヴェンシュタイン距離を求める時と似た感じで）
yahooは循環しているのでo->yへの遷移も出来る。
循環するため空文字は使わず、oyahoとした。
このままやるとおかしくなるので、[i][0] = iとして一文字だけoがある場合は取り除けるようにした。
こうすると次に[i][0]が更新される際には、yahoまで埋めたところからの遷移となるためうまくいく。

 public static void solve() {
        //longを忘れるなオーバーフローするぞ
        String s = next();
        N = s.length();
        int[][] dp = new int[N + 1][5];
        fill(dp, INF);
        for (int i = 0; i < 5; i++) {
            dp[0][i] = i;
        }
        for (int i = 0; i < N + 1; i++) {
            dp[i][0] = i;
        }
        String ya = "oyaho";
        for (int hi = 1; hi < N + 1; hi++) {
            for (int z = 0; z < 3; z++) {
                for (int wi = 0; wi < 5; wi++) {
                    //上
                    dp[hi][wi] = min(dp[hi][wi], dp[hi - 1][wi] + 1);
                    int nw = (wi - 1 + 5) % 5;
                    //左
                    dp[hi][wi] = min(dp[hi][wi], dp[hi][nw] + 1);
                    int cost = (s.charAt(hi - 1) == ya.charAt(wi)) ? 0 : 1;
                    //左上
                    dp[hi][wi] = min(dp[hi][wi], dp[hi - 1][nw] + cost);
                }
            }
        }
        System.out.println(dp[N][0]);
    }