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

A.YahooYahooYahoo(400)

問題

文字列 S が与えられる。yahooの文字列を0個以上繰り返してできる文字列との編集距離を求めよ。

  • 1 <= |S| <= 105

方針

ポイントは大きく2つ。他は普通の編集距離DPと変わらない(遷移については通常の編集距離と同じである)

  1. 取るべき状態数が限定されていることに気づくこと
  2. yahoo -> yahoo と遷移がループする

1. 取るべき状態数が限定されていることに気づくこと
編集先の文字列は yahoo の文字のループであるので、配列としては yahoo の 5文字分あればいい。yahooyahooyahoo となる場合は mod 5 の index を使用する。

2.yahoo -> yahoo と遷移がループする
例えば yahooahoo との編集距離を考えると、以下のようになる。

f:id:d_tutuz:20180825103226p:plain

1回目の遷移結果をもとに更新するパターンがあるためである。よって2回ループさせる必要がある。

       public void solve(int testNumber, InputReader in, PrintWriter out) {

            String src = in.nextString();
            int n = src.length();

            String tar = "oyaho";

            int[][] dp = new int[n+1][5];
            for (int i = 0; i < n+1; i++) {
                Arrays.fill(dp[i], INF);
            }

            for (int i = 0; i < n+1; i++) {
                dp[i][0] = i;
            }

            for (int i = 0; i < 5; i++) {
                dp[0][i] = i;
            }

            for (int i = 1; i < n+1; i++) {
                for (int j = 1; j < 10; j++) {

                    // 左
                    dp[i][j%5] = min(dp[i][(j-1)%5]+1, dp[i][j%5]);

                    // 上
                    dp[i][j%5] = min(dp[i-1][j%5]+1, dp[i][j%5]);

                    // 左上
                    int c = tar.charAt(j%5) == src.charAt(i-1) ? 0 : 1;
                    dp[i][j%5] = min(dp[i-1][(j-1)%5]+c, dp[i][j%5]);
                }
            }

            out.println(dp[n][0]);

        }

雑記

ループする場合には状態数が抑えられる。